[코딩/LeetCode150-(7)] Best Time to Buy and Sell Stock (121)

 

 

 

본 글은 LeetCode Top Interview 150에 정리된 문제를 요약하고 이에 대한 개인적인 풀이를 포함하고있습니다.
본 포스팅 시리즈는 150 list의 순서를 따라서 게재됩니다. 풀이 언어는 python을 사용합니다.

 

 

 

난이도: EASY

키워드: Array

 

 

문제

문제 원문: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&envId=top-interview-150 

 

prices라는 배열이 주어진다고하자. 이 배열의 i번째 원소들은 주식의 가격을 의미한다. 이 때 여러분은 주식을 사는 날과 파는 날을 정하려고한다. 가능한 거래 경우의 수 중 최대 이윤 값을 반환하라. (너무 당연하게도 매도는 매입 이후에 이루어져야한다.) 이윤을 낼 수 없는 경우 0을 반환해라.

 

풀이 

(Runtime: beats 99.83% of users with Python 3, Memory: beats 19.17 % of users with Python 3)

 

풀이 유도 사고의 흐름

max 값과 min 값을 각각 O(N)으로 구할 수 있으면 이 두 값이 min 값이 앞에있고 max 값이 뒤에 있다면 이 둘의 차를 통해 문제를 풀 수 있을거다. 하지만 이게 보장도 되지 않을 뿐더러 max와 min은 각각 O(N)이니까  (O(2N)이니까 실제 수행시간에서 손해) 이 둘을 한번에 찾는 방향으로 문제를 해결하는게 좋을 것 같다.

 

두 개의 값을 유지하면서 전체 배열을 순회하자. i번째 값이 min_val보다 작으면 min_val을 업데이트하고 i번째 값이 max_val보다 크면 max_val을 업데이트하자. max_val을 업데이트할 때는 max_val을 별도로 업데이트할 필요가 없지만 min_val을 업데이트할때는 max_val도 없던일로 만들어야한다. 따라서, 지금까지 가지고있는 max_val과 min_val의 차를 ans값에 업데이트 한 후 max_val을 현재의 min_val로 업데이트해주는 형태로 전체 배열을 순회하자.

 

풀이 구현

class Solution:
    def maxProfit(self, prices: List[int]) -> int:

        min_val = max_val = prices[0]
        ans = 0

        for price in prices:
            if price < min_val:
                ans = max(ans, max_val - min_val)
                max_val = min_val = price
            elif price > max_val:
                max_val = price
        
        return max(ans, max_val - min_val)

 

시간 복잡도는 O(N), 공간 복잡도는 O(1)

 

 

Takeaway

 

다른 접근 방법 중의 하나로, 이 문제는 DP 문제로 풀 수 있다. 근데 문제 특성만을 분석해서 풀어서 다른 overhead 없이 더 빠른 수행시간으로 문제 해결할 수 있다.

 

 

📚 LeetCode 75 / Code Signal 풀이 보러가기