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

문제: Best Time to Buy and Sell Stock 

• 관련 토픽: Array, Dynamic Programming
• 난이도: Easy 
• 링크 https://leetcode.com/problems/best-time-to-buy-and-sell-stock

요구사항

• prices 배열은 i번째 날짜의 주식의 가격을 담음
• 정해진 하루에 주식을 사고, 주식을 산 시점 이후에 주식을 판매
• 주식을 구매, 판매하며 어떤 조합이 가장 큰 수익을 낼 수 있는지 탐색
• 수익이 발생하지 않는 경우에는 0을 반환  

조건

• 1 <= prices.length <= 10^5 (10만개) 
  • 10만개의 요소를 다루는 문제는 효율적으로 풀이 하는 것이 좋다 
  • O(n) ~ O(nlogn) 시간 복잡도의 풀이가 필요! 
• 0 <= pricese[i] <= 10^4
  
  • 최대값,최소값을 구할 때 값 초기화의 기준으로 사용 가능

풀이 

문제 태그에는 Dynamic Programming으로 나와있긴 하지만, 여기서의 해법은 두가지의 포인터를 가지고 문제를 해결했다. 

이 문제를 해결할때 접근한 방식은: 

• 지금 이 가격이 내가 지금까지 봐온 가격중에 가장 싼가? (주식 구매를 위해)
• 지금 이 가격으로 판매를 하면 지금까지 확인한 최대 이율보다 더 좋은 수익을 발생 시킬 수 있나? 

이 두개의 기준을 가지고 문제를 풀이했다. Two pointer + Greedy 가 섞인 해법이다. 

 

1. prices = [7,1,5,3,6,4] 라고 했을 때, buy와 sell이라는 포인터를 추가한다 

 

2. prices 배열을 순회하면서, 가장 싼 가격과 가장 비싼 수익을 낼 수 있는 것을 찾는다. 가장 싼 가격을 찾았을 때는, buy를 sell (주로 탐색하는 포인터)로 변경을 한다.  

 

3. sell의 값을 기준으로 현재 수익을 확인한다.

 

4. 수익이 현재 최고수익 변수인 maxProfit 값보다 큰지 확인한다.

 

5. 현재 수익이 maxProfit보다 더 큰 경우, maxProfit의 값을 변경한다.

 

6. 남은 요소들중에 더 큰 수익을 낼 수 있는지, sell은 배열의 끝까지 탐색한다.

 

코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        buy, sell = 0, 1
        maxProfit = 0

        while sell < len(prices):
            if prices[buy] < prices[sell]:
                maxProfit = max(maxProfit, prices[sell] - prices[buy])
            else:
                buy = sell 
            sell += 1 

        return maxProfit

시간복잡도, 공간 복잡도

시간 복잡도: O(n)

• 입력값의 길이에 따라 루프를 탐색 하므로 O(n)
• sell은 prices의 모든 요소에 대해 한 번씩만 탐색!  n번 반복

공간 복잡도: O(1)

• 입력값인 prices를 제외하고, maxProfit, buy, sell 변수만 사용해서 공간복잡도는 상수