LeetCode - The World's Leading Online Programming Learning Platform

문제 풀이 아이디어

문제의 조건

이 문제가 요구하는 조건을 정리하면 아래와 같다.

1. 주식이 싼 시점 i와 주식이 비싼 지점 j를 찾을 것 (단, i < j)
2. prices[j] - prices[i]를 극대화 할 것
3. 1, 2의 조건을 O(N)의 코드를 활용할 것

순회하면서 최저가, 최대 이익을 갱신

O(N)의 시간복잡도로 문제를 풀기 위해서는 반복문을 1번만 사용해야 한다. 따라서 prices 배열을 처음부터 순회하면서 최저가와 최대 이익을 갱신해가면 된다.

먼저, 과거의 최저가 대비 현재 가격에 팔았을 때와 현재까지의 최대 이익을 비교해서 최대 이익을 갱신하는 작업을 한다.

그리고 과거의 최저가와 현재 가격을 비교하여 최저가를 갱신하는 작업을 하면 된다.

코드

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        var minPrice = prices[0] // 현재까지 최저가
        var profit = 0 // 현재까지 최대 이익 (음수이면 0을 리턴해야 하므로 초기값 0)
        
        for price in prices {
            profit = max(profit, price - minPrice) // 최대 이익 갱신
            minPrice = min(minPrice, price) // 최저가 갱신
        }
        
        return profit
    }
}