Python으로 푸는 LeetCode 121. Best Time to Buy and Sell Stock (Easy)

LeetCode 121. Best Time to Buy and Sell Stock (Easy)

이 문제는 주어진 prices만큼 그날의 가격을 알 수 있다고 했을 때, 

단 한번, 주식을 사고 단 한번 주식을 팔 수 있다고 했을 때

최대 수익을 얼마를 얻을 수 있는지 반환하는 코드를 짜야한다.

LeetCode에서 푼 문제 리스트 보기

LeetCode에서 문제 보기

github에서 코드 보기

문제 풀이

딱 한번 사고 팔 수 있기 때문에 가장 좋은 경우는 prices안에서 최소값의 index가 최대값의 index 보다 항상 작은 경우이다.

하지만 그렇지 않은 경우일 확률이 더 높다. 그렇게 되면 반드시 최대값과 최소값의 차이가 최대 수익이 아닐 수도 있다.

예를 들어보자,

prices = [9,2,3,8,1,5]

최대값은 9이고 최솟값은 1이지만, 최대값의 index가 최솟값의 index보다 크다.

그리고 최대 수익은 2일때 사고 8일때 팔아서 생긴 6만큼이 최대수익이다.

첫번째 파이썬 코드에 대한 리뷰.

처음 작성한 코드는 효율이 좋지 않다. prices를 notation으로 분리하여 그 범위 내에서 최대값을 찾아 값을 비교하는데 활용한다.

만약 최댓값이 중간에 있을 경우에는 비교하고 있는 원소 최댓값의 위치가 동일해질 경우(즉, 위 예에서 볼때, 8이 최대값이었는데 현재 비교하려는 원소가 8의 차례가 되었을 경우)에는 나머지 뒷부분에서 최댓값을 다시 구하는 방식이다.

두번째 파이썬 코드에 대한 리뷰.

개선한 파이썬코드에서는 다른 사람의 코드를 가져와서 이해해보았다. 파이썬의 기본 모듈인 (min)heapq에서는 항상 0번째 원소가 현재 heapq에 든 값들 중에 가장 최소값이 라는 성질을 이용하였다. 첫번째 코드와 비교해보았을 때,  현재의 원소와 비교할 최대값을 구하기 위해 뒷부분의 모든 원소들을 순해해야만 했다면, 두번째 파이썬 코드는 prices를 순회할 때, 현재의 원소가 최댓값이라는 가정 하에, heapq의 첫번째 원소(가장 최솟값)과 차익을 비교하여 그 가운최대 수익을 쉽게 구할 수 있었다.

파이썬 코드

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        """
        Runtime : faster than 5.62%
        Memory Usage : less than 5.08%
        """
        last_idx = len(prices) -1
        max_profit = 0
        max_index = -1
        max_v = -1
        for idx, p in enumerate(prices):
 
            if idx < last_idx and p > prices[idx + 1]:
                continue
 
            # 새로운 최대값을 찾는다
            if max_index <= idx:
                temp = prices[idx+1:]
                if temp:
                    max_v = max(temp)
                    max_index = (idx + 1) + temp.index(max_v)
                else:
                    max_v = -1
                    max_index = -1
 
            if p < max_v:
               profit = max_v - p
               if max_profit < profit:
                max_profit = max_v - p
        return max_profit

파이썬 코드 - 개선

import heapq
 
class Solution(object):
    def maxProfit(prices):
        """
        Time    O(nlogn)
        Space   O(n) heap
        """
        if len(prices) < 2:
            return 0
        pq = []
        diff = 0
        for price in prices:
            heapq.heappush(pq, price)
            if price - pq[0] > diff:
                diff = price - pq[0]
        return diff

#LeetCode 121 Best Time to Buy and Sell Stock #LeetCode 121 Python #LeetCode 121 파이썬