[Leet Code풀이] 121. Best Time to Buy and Sell Stock

문제 설명

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

주식에서 한번 샀다 팔았다 해서 최고 수익이 얼마나 날 수 있는지를 계산한다.

풀이

접근 방법.

한번 샀다 팔았을때 최대 수익률만 구하면 되니깐, 최저점과 최고점의 차를 구하면 된다. 다만 주어지는 리스트가 시간순서대로 오기때문에 이를 고려해주어야 한다. 알고리즘이 간단하므로 바로 코드로 설명해보겠다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0                # 초기 이익은 0
        lower = 100000            # 최저점은 일단 문제 TC에서 가장 큰 값을 할당한다.
        for v in prices:
            if v < lower:         # 최저점을 갱신
                lower = v
            if v - lower > 0 and profit < v - lower:    # 현재 값과 lower의 차가 profit보다 크다면 이를 갱신한다. 
                profit = v - lower
        return profit             # 맨 마지막 루프까지 돌았을때 남은 profit이 최고 이익이다.

위 풀이의 시간 복잡도와 공간복잡도는 아래와 같다.

• 시간 복잡도 : O(N) nums만큼 루프를 도므로 O(N)

• 공간 복잡도 : O(1) 추가적인 공간을 사용하지 않는다.