[LeetCode] 121. Best Time to Buy and Sell Stock

문제

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

Best Time to Buy and Sell Stock - LeetCode

 

잠깐

"1. Two Sum" 문제 처럼 이중 for문으로 구현할 경우 시간 초과가 발생합니다.

단순 이중 for문 보다 더 효율적으로 구현하라는 말이죠.

그럼 이중 for문의 종료 시점 혹은 단일 for문, DP에 대해서 생각해볼 필요가 있겠네요.

 

코드

class Solution {
    func maxProfit(_ prices: [Int]) -> Int {
        
        var maxProfit: Int = 0
        var buyPrice: Int = prices[0]
    
        for day in 1..<prices.count {
            var nextDayPrice: Int = prices[day]
            var profit: Int = nextDayPrice - buyPrice
        
            if profit > 0 {
                maxProfit = max(maxProfit, profit)
            } else {
                buyPrice = nextDayPrice
            }
        }
        return maxProfit
    }
}

 

설명

코드는 쉬우니, 로직 위주로 설명할게요.

 

다음과 같은 배열이 존재한다고 해보죠. (아이패드로 그려봤는데, 잘나오네요)

인덱스 0번째의 값인 5를 기준으로 이후 값들과 비교해볼게요

이번엔 5보다 작은 인덱스 5번째 값인 3을 기준으로 이후 값들과 비교해볼게요

눈치 채셨나요? 이번엔 5보다 작은 3보다 작은 1을 기준으로 이후 값들과 비교해볼게요

보시는것과 같이, 비교 기준 값이 변경되면, 더이상 비교할 필요가 없어집니다.

비교 기준이 5인 경우 4와 비교하면 차이값은 -1을 갖게 되죠.

비교 기준이 3(5보다 작은)인 경우 4와 비교하면 차이값은 +1을 갖게 되죠.

비교 기준이 1(5보다 작은)인 경우 4와 비교하면 차이값은 +3을 갖게 되죠.

따라서, 현재의 비교 기준값(ex. 5)보다 낮은 값(ex. 3)이 나온 순간, 현재의 비교 기준값(ex. 5)과 이후 값들의 비교는 의미가 없어집니다.

 

주식하시는 분은 공감 할텐데,

구매한 가격보다 오늘의 가격이 더 저렴한 경우 "오늘 살걸!!"이라고 생각들잖아요.

그리고 다음날, 가격이 더 떨어지면 "오늘 살걸!!"이라고 생각해보신적 있으시죠?

 

결과적으로 현재 기준값보다 낮은 값이 나오면, 비교값을 변경하고, 변경된 비교값으로 비교해 나가면 됩니다.

로직을 그림으로 그려보면 다음과 같습니다.

for문 1개로 구현이 가능하네요.

 

회고

다음은 21년 3월에 구현한 코드에요.

오늘 구현한 코드와 거의 유사하죠? 신기하네요.

 

다시 보니, 변수명을 잘 모르겠네요;;;;;;;

역시나 변수명에 대해 반성합니다. ( _ _ )

class Solution {    func maxProfit(_ prices: [Int]) -> Int {
        var minPrice = prices[0]
        var maxValue = 0
        
        for i in 1..<prices.count {
            var currPrice = prices[i]
            if currPrice < minPrice {
                minPrice = currPrice
            } else {
                let value = currPrice - minPrice
                if maxValue < value {
                    maxValue = value
                }
            }
        }
        return maxValue
    }
}