[LEETCODE 150] - 121 Best Time to Buy and Sell Stock

LeetCode의 121번 문제인 "Best Time to Buy and Sell Stock" 문제이다

이문제는 Twopointer + 그리디 알고리즘방식으로 풀어봤다 " 항상 가장 싼 매수 시점을 유지하면서, 매일 매도 후보를 앞으로 움직이는 방식" 이다

Greedy Algorithm(탐욕 알고리즘)

 

탐욕 알고리즘 이란?

• Greedy Algorithm: 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫒아 최종적인 해답에 도달하는 방법

동적 프로그래밍 사용시 지나치게 많은 일을 한다는것에서 착안하여 고안된 알고리즘 이다.

 

알고리즘 아이디어

l = 매수(buy) 후보 인덱스 (지금까지 본 것 중 "가장 싸게 살 수 있는 날"로 유지)

r = 매도(sell) 후보 인덱스 (현재 날짜, 하루씩 앞으로)

 

매일 r을 보면서

1. 만약 prices[l] < prices[r] 이면 l에 사고 r에 팔면 이익이 양수니까, profit = prices[r] - prices[l] 계산해서 maxP 갱신

2. 아니면 (prices[l] >= prices[r]) 지금 r의 가격이 더 싸거나 같다는 뜻 → 더 좋은 매수 기회

(왜냐면 이후에 팔더라도 더 싸게 산 쪽이 이익이 더 커지니까) 그리고 r += 1로 끝까지 진행

정답 코드(Python)

class Solution: 
	def maxProfit(self, prices: List[int]) -> int:
    
    l, r = 0, 1
    maxP = 0
    
    while r < len(prices):
    	if prices[l] < prices[r]:
        	profit = prices[r] - prices[l]
            maxP = max(maxP, profit)
        else:
        	l = r
           r += 1
        return maxP

 

풀이 해석

1. 첫날 (0일)을 매수 후보로 두고, 다음날(1일)부터 매도 후보로 탐색 시작, 최대 이익은 일단 0 (거래 안하면 0)

l , r = 0, 1
maxP = 0

 

2. 매도 후보 날짜 r을 끝까지 한번만 훓는다 

while r < len(prices):

 

3. 매수가가 더 싸면 = 지금팔면 이익이 남는다, 그 이익으로 maxP를 갱신한다.

if prices[l] < prices[r]:
	profit = prices[r] - prices[l]
    maxP = max(maxP, profit)
else: 
   l = r

 

4. 매도가 후보가격이 더싸거나 같으면 , 지금까지 잡아둔 매수후보 l보다 더 싼날을 발견하여 앞으로는 여기서 사는게 무조건 유리하니까 매수 후보를 r로 교체

r += 1
return maxp

 

5. 다음 날짜로 매도 후보 이동하고 끝까지 본후 최대 이익 반환한다.

 

시간 복잡도 : O(n)

 

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