[LeetCode]Best Time to Buy and Sell Stock

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

Best Time to Buy and Sell Stock - LeetCode

 

문제 분석

주식에 대한 가격이 주어졌을 때 가장 많은 차액을 구하는 문제입니다. 이득을 얻을 수 없다면 0을 리턴합니다.

 

처음 시도한 답안

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        output = 0
        # 산 가격과, 판 가격을 기록하기 위한 리스트
        buy_and_sell_point = []

        # 반복문에서 다음 날에 접근하기 때문에 마지막 날 전까지 순회
        for index, price in enumerate(prices[:-1]):
            # 첫날 사고, 둘째날 파는 것으로 초기 값 할당
            if not buy_and_sell_point:
                buy_and_sell_point = [price, prices[index+1]]
                output = max(output, buy_and_sell_point[1]-buy_and_sell_point[0])

            else:
                # 파는 날짜만 갱신하는 케이스
                a = prices[index+1] - buy_and_sell_point[0]
                # 파고 사는 날짜 모두 갱신하는 케이스
                b = prices[index+1] - price
                # 갱신 안하는 케이스는 buy_and_sell_point 활용

                # 갱신 하는 케이스 중 더 큰 이익을 내는 값을 선택
                if a < b:
                    new_buy_and_sell = [price, prices[index+1]]
                    output = max(output, b)
                else:
                    new_buy_and_sell = [buy_and_sell_point[0], prices[index+1]]
                    output = max(output, a)

                # 산 날짜와 판 날짜의 가격 중, 적고 큰 것을 골라서 갱신.
                buy_and_sell_point = [min(new_buy_and_sell[0], buy_and_sell_point[0]), max(new_buy_and_sell[1], buy_and_sell_point[1])]

        return output

접근 방법

1. 산 가격과 판 가격을 기록하기 위한 리스트를 만듭니다. 이 리스트에는 항상 2개의 값만이 들어가 있으며,
   가장 싸게 산 가격과 가장 비싸게 판 가격을 갱신하는 용도입니다.
2. 초기 값은 첫날 사고, 둘째날에 파는 것으로 할당합니다.
3. 다음날 부터는 아래의 3가지 경우중 가장 극대화된 이익을 골라서 갱신합니다.
   1. buy_and_sell_point에 저장되어있는 산 가격 & 판매한 가격
   2. 산 날짜는 그대로 두고 파는 날짜만 갱신하는 경우
   3. 파고 사는 날짜 모두 갱신하는 경우
4. 산 날짜와 판 날짜의 가격중, 싸게 사고 비싸게 판 가격을 골라서 buy_and_sell_point를 갱신합니다.

반복문을 순회하면서 다음날짜까지 고려한 경우, 발생하는 3가지의 경우의 수에서 이익이 극대화 되는 지점을 찾아서 해결한 문제입니다. 

다만, 코드 자체가 불필요한 부분들이 많이 있어 최적화를 해보았습니다.

 

두번째로 시도한 답안 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        min_purchase = prices[0]

        # 첫날에 사자마자 파는 것은 불가능하므로 첫날 제외하고 순회
        for index, price in enumerate(prices[1:]):
            # 이익이 극대화 되는 값을 갱신
            max_profit = max(max_profit, price-min_purchase)
            # 가장 싸게 구매한 가격을 갱신
            min_purchase = min(min_purchase, price)

        return max_profit

접근 방법

1. 첫번째 방법과는 달리, 최대 이익과 최소 가격을 추적합니다.
2. 첫날에 사자마자 파는 것은 불가능하므로 첫날은 제외합니다.
3. 반복문을 순회하면서 이익이 가장 극대화 되는 값을 max_profit에 갱신합니다.
4. 가장 싸게 구매한 가격을 갱신합니다.

최소 가격을 갱신하면서 현재까지의 최대 이익과 현재 등장한 가격-최소 가격 중 큰 값을 선택하여 저장합니다.

즉, 이전보다 더 싼 가격이 등장한 이후에 판매한다면 이익이 커지는지를 생각합니다. 커지지 않는다면 이전까지의 최대 이익값을 고르면 됩니다.

 

제가 시도했던 답안에 비해 굉장히 간결하고 이해하기도 쉬워졌습니다.