[Greedy][Easy] 121. Best Time to Buy and Sell Stock

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description

 

 

Q. 주가의 각 날에 해당하는 가격 prices 배열이 주어진다. 

이때 단, 하루 사서 다른 날 판다면, 이 최대 이익을 구하라. 

 

 

Solution. 

 고전이지만 좋은 문제다. 

 2 중 for loop를 쓰면 간단하겠지만, 

 그 답을 원하는 것은 아니다. 

 

 trick 같은 사고의 전환이 다소 필요하다. 

 

 loop을 돌면서 최소 가격을 갱신한다. 

 현재 가격에 이 최소 가격을 제하여 판매가격을 만들고 이 최대값을 저장한다. 

 이 최대값이 우리가 원하는 값이 된다. 

 

 최소값은 이 값을 근거로 추후 값에 차감을 해야만 의미가 있는데, 이 방식은 최소값과 그 차이값을 매번 하므로, 이에 부합한다. 

 또한 현재 최소값 기준이 아닌 이전 최소값에서 최대 이익을 만들었더라도, 현재 이익보다 이전이 더 크면 그대로 보존되므로, 문제의 모든 요건을 만족한다 할수 있겠다. 

 

로직을 코드로 써 본다. 

 

int maxProfit(vector<int>& prices) 
{   
    int buy = INT_MAX;
    int sell = INT_MIN;
    for(int q = 0; q < prices.size(); ++q)
    {           
        buy = min(buy, prices[q]);
        sell = max(sell, prices[q]-buy);
    }
    return sell;
}

 

 

적당한 결과를 얻었다. 

 

Note ) 로직 적응력을 키우기 위해서 관련 variation 문제를 찾아 보자.