[Leetcode/Easy] 주식을 사고팔기 가장 좋은 시점 (121. Best Time to Buy and Sell Stock, Swift)

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

 

🤔 문제 설명

prices[i]는 지정된 i 날의 주식 가격을 포함하고 있는 리스트입니다.

여러분은 한 주식을 살 날을 선택하고 그 주식을 팔기 위해 미래에 다른 날을 선택함으로써 여러분의 이익을 극대화하고자 합니다.

이 거래에서 얻을 수 있는 최대 이익을 반환하세요. 이익을 얻을 수 없으면 0을 반환하십시오.

[7,1,5,3,6,4]
// 5 : 2일차 1일 때 사서 5일차 6일 때 팔면, 5의 이익을 얻는다.

 

💡 풀이

주식에서 최대 이익을 얻으려면, 기본 전제는 "최저가"에서 구매해 "최고가" 지점에서 팔아야 한다.

그래서 각 시작점을 기준으로 끝에 까지 반복을 돌았을 때 만날 수 있는 최고가가 언제인지를 배열에다 저장했다. 예시 코드의 경우 만날 수 있는 최고가는 [7, 6, 6, 6, 6, 4]가 되겠다. 
반복을 거꾸로 돌면서 최대값을 누적해서 계속 구하는 형태라고 생각하면 되겠다!

이후 기존 배열과 차이를 구한다면, 그것이 각 부분에서 얻을 수 있는 최대 이익이 되겠다.
[7, 6, 6, 6, 6, 4]에서 입력 배열인 [7, 1, 5, 3, 6, 4]를 빼면 [0, 5, 1, 3, 0, 0]으로 최대 이익이 5인 것을 찾을 수 있었다.

 

🧑🏻‍💻 코드 (Swift ver.)

💡 Runtime : 275ms (Beats 84.90%), Memory : 19.34MB (Beats 16.51%)

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        // 구간별 최대값 구하기
        // index = 1 (1~prices.count-1까지 범위 중 가장 큰 값)
        var maxPrices = [Int](repeating: 0, count: prices.count)
        var maxPrice = 0 
        for index in (0..<prices.count).reversed() {
            maxPrice = max(maxPrice, prices[index])
            maxPrices[index] = maxPrice
        }

        // 기존 값과 가장 큰 값을 비교해서 최대 이익 찾기
        var maxProfit = 0
        for index in 0..<maxPrices.count {
            var profit = maxPrices[index] - prices[index]
            maxProfit = max(maxProfit, profit)
        }

        // 최대 이익 반환
        return maxProfit
    }
}