[Java Script]LeetCode 121. Best Time to Buy and Sell Stock

1. 문제 개요

문제 링크 : 121. Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock - LeetCode

• 주어진 배열은 주식을 거래하고 팔 수 있는 날자별 수익이다.
• 해당 기간에서 얻을수 있는 가장 큰 수익이 얼마인지 알아내시오
• 단 날짜별이기에 미래의 시간에서 구매해서 과거에 판매할 수는 없다. 

2. 문제 풀이

처음 이문제를 접했을 때는 라운드 로빈 토너먼트(round-robin tournament) 방식 이용해서 해결하려 하였으나 시간복잡도 상에서 효율이 좋지 않은 반복문 안에 반복문을 집어넣지 않을 방법을 고민하다 새로운 해결책은 찾았습니다.

 

한 번의 반복문이 도는 동안

각 배열을 탐색하는 과정에서 후속값이 앞전 값보다 작을 때마다 최고 수익값을 갱신시키고 이때 가장 높은 수익이 나오는 값을 찾는 방법을 통해 구현하였습니다.

 

 

이를 구현하기 위해 주석으로 코드의 구조를 잡아보면 다음과 같은데

var maxProfit = function(prices) {
    let now = 0, min = prices[0], max = 0
	// 배열 탐색 반복문 
    // 이전 값보다 후속값이 작은경우 값을 갱신
    // 최저점 에서의 수익률이 현재의 수익률 보다 높을때마다 갱신
};

 

LeetCode 요구 양식으로 코드 구현

var maxProfit = function(prices) {
    let now = 0, min = prices[0], max = 0
    // 원래 for문을 사용하는것이 효율이 더 좋지만
    // 기존 라운드 로빈 토너먼츠 방식에서 방복문의 중복을 피하기위해 while을 사용 했기에
    // 연장선으로 while로 구현하였습니다.
    while(now < prices.length){
        if(prices[now] < min) min = prices[now]
        if(prices[now] - min > max) max = prices[now] - min
        now++
    }
    return max
};

 

 

LeetCode 제출 결과

 

이렇게 구현에 성공하였습니다.

 

3. 시간 복잡도 계산

splice의 시간복 작도가 O(n)입니다.

O(n) = O(n)

 

4. 개선 사항

시간 복잡도의 효율화를 위해 이중 반복문을 최소화 할 수 있도록 개선사항을 만들었고 효과적으로 적용할 수 있었습니다.

 

5. 깃허브

관련 사항은 깃허브에 모두 기재되어 있습니다.