121. Best Time to Buy and Sell Stock

문제링크: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

Problem

문제를 살펴보자면, 어떤 주식의 가격이 리스트로 주어지고, 그 중 최대 수익을 찾으면 되는 아주 간단한 문제입니다.
리스트는 시간순이며, 사고 파는 것은 한번씩만 됩니다.

예를 들어 조금 더 살펴보겠습니다.

prices = [7,1,5,3,6,4]

라는 주식의 값이 리스트로 주어졌을때, 그리고 각 값이 하루 단위라고 생각했을때, 둘째 날에 사서 다섯째 날에 팔면 되는 구조입니다.

Solution

1. Brute Force
   첫 접근은 브루트포스로 접근을 했습니다.
   결론부터 얘기하자면, 시간초과가 떴고, 그래서 따로 코드를 기재하지는 않겠습니다.
   간단하게 풀이를 설명하자면, 이중 루프를 돌면서 모든 gap을 확인하는 겁니다.
   그중 가장 gap이 큰 값을 리턴하면 됩니다.

2. Two Pointer
   투포인터로 접근하면 쉽게 풀립니다. 최저점에 한 포인터를 두고, 다른 포인터를 전진시키며 가격을 비교하면 되니까요.

   class Solution:
   def maxProfit(self, prices: List[int]) -> int:
       min_price = prices[0]
       max_return = 0
       
       for i in prices:
           min_price = min(min_price,i)
           max_return = max(max_return, (i - min_price))
       
       return max_return

   설명에 비해 비교적 짧은 코드입니다. 명시적으로 right,left나 start,end 같은 포인터를 만들어 쓰진 않았지만, min_price와 반복문의 i 가 포인터라고 생각하시면 됩니다.