파이썬 알고리즘 인터뷰 12번 주식을 사고 팔기 가장 좋은 시점 (리트코드 121번)

Kim Yongbin·2023년 8월 18일

코딩테스트

목록 보기

12/162

Problem

LeetCode - The World's Leading Online Programming Learning Platform

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

주어진 배열은 i번째 날의 주식의 가격을 의미한다. 특정 날에 사서 다른 날에 판다고 하였을 때 얻을 수 있는 최대 이익을 구하여라. 이익을 낼 수 없다면 0을 리턴하라.

Solution

풀이1 - 브루트 포스

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)

        max_profit = 0
        for i in range(length - 1):
            for j in range(i+1, length):
                max_profit = max(max_profit, prices[j] - prices[i])

        return max_profit

너무나 당연하게도 Time out.

풀이 2 - 브루트 포스 최적화(?)

from typing import List

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

        return max_profit

for 문 대신 max()를 중첩하여 풀었지만, 파이썬에서 max() 함수는 O(n)의 시간 복잡도를 가지고 있다. 즉, 해당 풀이도 시간 복잡도가 $O(n^2)$ 으로 Time out이 발생한다.

해설 1

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        min_value = prices[0]
        for price in prices:
            if min_value > price:
                min_value = price
            elif price > min_value:
                if price - min_value > max_profit:
                    max_profit = price - min_value

        return max_profit

반복문을 돌면서, 새로운 원소의 값이 현재의 min_value보다 작으면 min_value를 바꿔주고, 새로운 원소의 값이 min_value보다 크고, 그 차이가 현재의 max_profit보다 크면 max_profit을 업데이트를 해준다.

해설 2 - 기술 통계학

저점을 기준으로 가격 차이를 계산하고, 만약 그 차이가 현재의 최대 크기보다 클 경우 교체해나가는 형식으로 풀면 되는 문제이다.

from typing import List

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        profit = 0
        min_price = sys.maxsize

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