본문 바로가기
코딩 공부

Leetcode Best Time to Buy and Sell Stock II 파이썬 시도

by 카우보이연구소 2022. 1. 12.

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

처음 이 문제를 보았을 때는, Easy (medium이네요...) 등급 임에도 불구하고 약간 어려웠습니다. 아무래도 programming 논리가 잘 머릿속에 정리가 잘 안 되어있다 보니까 힘드네요.

 

Best Time to Buy and Sell Stock II 문제입니다. 말 그대로 언제 주식을 팔고 사는 것이 돈을 제일 많이 벌 수 있는가 입니다.

주어진 것은 prices[i] 리스트가 주어집니다 (List[int]). 그리고 int value를 return 해야죠.

 

처음에는 막막했습니다. 처음에 들었던 생각은, "모든 경우의 수를 만들어보자"였습니다.

 

 

 

그리고 풀리지 않아서 solution을 보게 되었습니다. ㅠㅠ

 

solution에서 추천한 방법은, 'peak'과 'valley'를 찾는 것이었습니다. (peak는 정상? 옆의 숫자들 중 높은 것, valley는 낮은 숫자) [또는, peak = 다음 숫자가 index i의 숫자보다 낮다면 / valley = 다음 숫자가 index i의 숫자보다 높다면]

 

이를 활용한 제가 적은 python code는 이와 같습니다:

class Solution(object):
    def maxProfit(self, prices):
        maxprofit = 0
        i = 0
        valley = prices[0]
        peak = prices[0]
        while i < (len(prices) - 1):
            while (i < (len(prices) - 1) and prices[i] >= prices[i+1]):
                i += 1
            valley = prices[i]
            while i < (len(prices) - 1) and prices[i] <= prices[i+1]:
                i += 1
            peak = prices[i]
            maxprofit += peak - valley
        
        return maxprofit

논리를 설명하자면, index = i가 리스트를 벗어나지 않는 상태에서 (첫 while loop), prices[i] < prices[i+1]인 경우의 'valley'를 찾고(두 번째 while loop), 그리고 prices[i] > prices[i+1] 경우의 'peak'를 찾는 것입니다 (세번째 while loop).

 

그 후, profit에 peak에서 valley를 뺀 이익을 계속 더해주는 것이죠.  

 

오류가 계속 났었는데, 이유는 두번째 while loop에서 (i < len(prices)-1)을 앞에 안 둬서 자꾸 i+1가 list 바깥은 탐색하느라 문제가 생겼었습니다.


또 다른 방법으로는, 전의 peak와 valley 개념과 비슷합니다. 다만, valley에서 peak로 가는데, 올라가는 것의 총합이 peak - valley의 값과 같아 더 심플한 코드를 작성할 수 있다는 것입니다.

class Solution(object):
    def maxProfit(self, prices):
        max_profit = 0
        
        for i in range(1, len(prices)):
            if (prices[i] > prices[i-1]):
                max_profit += prices[i] - prices[i-1]
                
        return max_profit

하지만, 속도는 어쩔 수 없이 위의 방법보다는 느렸습니다.


이렇게, 두 가지 방법이 있었습니다! ( 둘 다 O(n) )

 

Best Time to Buy and Sell Stock II - LeetCode

Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.

leetcode.com

 

댓글