[LeetCode] 121. Best Time to But and Sell Stock (C++)

문제

 

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

Best Time to Buy and Sell Stock - LeetCode

 

풀이

 

난이도: Easy

 

간단한 배열 문제.

 

미래에 산 주식을 과거에 팔 수는 없으니 현재 시점(day)이나 그 이전에 구매한 주식을 미래에 팔아야 한다.

 

 

마지막 날을 Dday,  현재를 day라고 하고 배열을 역순으로 진행해보자.

Dday에서 day를 첫 번째 날(과거)로 한 칸씩 움직이면서 (day~Dday)에서 얻을 수 있는 최대 수익을 구할 것이다.

 

이때 (day~Dday) 사이에서 파는 가격(sell)과  사는 가격(buy)을 정해야 한다.

초기의 sell은 (day~Dday) 사이 최대 주가, buy는 (day~Dday) 사이의 최소 주가로 설정된다.

 

sell과 buy은 day가 첫 날로 역행하면서 변동이 되는데,

현재(day)의 주가가 현재의 buy 보다 작다면 buy를 현재의 주가로 정하는 것이 최선의 선택이 된다.

이때의 최대 수익은 sell - buy로 구할 수 있다.

 

반대로 day의 주가가 sell보다 높다면 (first day ~ day)사이에서 산 주식은 day+1 이후의 날에는 팔 필요가 없다.

이는 현재(day)의 주식이 미래의 어느 시점의 가격보다 높다면 과거에 산 주식에서 최대 수익을 내기 위해서는 현재에 팔아야 하기 때문이다.

따라서 day부터는 sell과 buy는 day의 주가로 바꾸어 더 이상 (day +1 ~Dday)의 주가는 계산에서 배제해준다.

 

 

이와 같이 역순으로 배열을 한 번만 순회하여 답을 구할 수 있다.

 

 

 

 

코드