[Leetcode/파이썬] 121_Best Time to Buy and Sell Stock 문제풀이

문제 설명

 

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

 

 

사고 흐름

1. 문제 읽고 자연스럽게 스택, 투포인터 생각남

2. 투포인터 left(최저), right(최대) 를 사용해 최대값을 찾

 

문제 핵심과 알고리즘

투포인터를 활용한 최대와 최소 찾기

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        m = 0
        left, right = 0, 1
        while left<right and left<len(prices) and right<len(prices) :
            if prices[left]<=prices[right] :	# 주식 증가 
                m = max(m, prices[right]-prices[left])
                right+=1
            else :	# 주식 감소
                left=right
                right+=1
        return max(m, 0)

 

left와 right를 사용해 초기값(left)보다 크면(주식이 증가하면), 그 증가된 값이 최대인지 확인한다. 만약 감소했다면(left 보다 더 작은 값이라면) 해당 값으로 이동한다. 

 

다른 풀이 및 총평 

p = 0
min_price = -sys.maxsize

for price in prices :
	min_price = min(min_price, price)
	p = max(p, price-min_price)

 

이렇게 쉬운 방법이 있었다니.. 

완전탐색, 이동하면서 최소값 갱신, 그에 따른 최댓값 갱신 이라는 아이디어는 동일하지만 코드가 이렇게 다르다니..! 

내가 투포인터에 집착하면서 당연히 while문을 썼다. 이렇게 이쁜 for문이 있었는데..!  

그리고 자꾸 최대, 최소 문제를 보면 완전 탐색을 거부(?)하려고 하는데.. 보통 완전 탐색인 경우가 많은 것 같다.