[Leet code - 121] Best Time to Buy and Sell Stock ✅

문제

Input : 주식 시세가 나열된 정수 배열 prices

※prices[i] = i번째 날의 주식 시세

 

Output : 한 번의 거래로 얻을 수 있는 최대 이익

 

시간 복잡도

※1초에 1억번을 대략적인 기준으로 삼는다.

 

최소 연산해야할 단위는 prices의 원소이므로, 자연스럽게 n은 prices의 길이가 된다.

$1 \le n \le 10,000$

 

• $O(n^2) = 100,000,000$ ❌
• $O(n \log n) \approx 130,000$ ✅
  $n \log n$이하의 복잡도를 목표로 풀이한다.

 

해결 계획

2차 반복문은 복잡도면에서 불가능하고, 원소의 순서가 중요하기 때문에 정렬도 큰 의미가 있지는 않다.

그래서 O(n)단에서 뭔가 저장하면서 하면 될 것 같기도 해서, 어떤걸 저장해야하는지에 대해 좀 고민했다.

 

간단하게 생각을 해보니까 최소값과 최대값만 찾으면 되는 문제였다.

근데 문제는 최대값이 최소값보다 앞에 있으면 안된다는 점이다.

 

그래서 각 날마다까지의 최소 값을 저장하면 되지 않을까? 라고 생각했고,
해당 값들은 한 번 순회를 하면서 충분히 계산할 수 있기 때문에 괜찮다고 생각했다. 

그리고 자연스럽게 각 날마다까지의 최대 이익도 도출이 되어서 해당 방향성으로 진행하기로 했다.

 

아래는 대략적인 수도코드다.

dp[i] = i번째 날까지의 최소값

int maxValue;
for (int i ; i < prices.size)
{
    if (prices[i - 1]의 최소값과 현재 값 prices[i] 비교)
    {
    	prices[i]가 크면, 최소값도 유지되기 때문에 이득 계산
        maxValue = std::max(maxValue, 이득)
    }
    prices[i]기 작으면, 최소값을 자기자신으로 함 => 이득은 없기 때문에 바로 넘어간다.
}

return maxValue;

 

수도코드를 작성하면서 각 날마다까지의 최대 이익이 아닌, i일의 시세에 팔 경우 가질 수 있는 최대 이익으로 변경했다.

그 후 해당 코드로 예제를 한 번 시뮬레이션 했다.

prices = [7,1,5,3,6,4]

i = 0 / 7 (초기값으로 자기자신 세팅)
dp [7, 0, 0, 0, 0, 0]
이익 : 0

i = 1 / 7 ? 1 (더 작으므로 자기자신 설정)
dp [7, 1, 0, 0, 0, 0]
이익 : 0

i = 2 / 1 ? 5 (더 크므로 계승)
dp [7, 1, 1, 0, 0, 0]
이익 : 4

i = 3 / 1 ? 3 (더 크므로 계승)
dp [7, 1, 1, 1, 0, 0]
이익 : 2

i = 4 / 1 ? 6 (더 크므로 계승)
dp [7, 1, 1, 1, 1, 0]
이익 : 5

i = 5 / 1 ? 4 (더 크므로 계승)
dp [7, 1, 1, 1, 1, 1]
이익 : 3

최대 이익 : 5

 

 

 

 

구현

구현하면서 굳이 배열을 만들어서 최소값들을 모두 저장하지 않아도 충분히 진행이 되어서,
int형 변수 두 개를 이용하여 DP에서 Greedy 방식으로 변경했다.

int maxProfit(vector<int>& prices) {
    int result = 0;
    int minVal = prices[0]; // 초기값 세팅

    for (int i = 1; i < prices.size(); ++i)
    {
        if (minVal < prices[i])
            result = std::max(result, prices[i] - minVal);
            
        else minVal = prices[i];
    }

    return result;
}

 

 

 

되돌아보기

코드 이해

사실 포스팅하면서 정리하기 전까지 각 날마다까지의 최대 이익을 저장하고 있는 줄 알았다.

근데 i일의 시세에 매도할 경우 가질 수 있는 최대 이익이였을 줄이야..

 

운 좋게 통과됐지만 확실하게 어떤 걸 의미하는지 잘 생각해봐야겠다.

 

 

개선 코드

분기를 없애, 조금 더 클린한 버전이다.

int maxProfit(vector<int>& prices) {

    int minVal = prices[0];
    int result = 0;

    for (int i = 1; i < prices.size(); ++i) {
        result = std::max(result, prices[i] - minVal);
        minVal = std::min(minVal, prices[i]);
    }

    return result;
}