[LeetCode 해석 및 풀이] 121. Best Time to Buy and Sell Stock

LeetCode 문제 해석 및 풀이 방법

 

문제 121. Best Time to Buy and Sell Stock(주식을 사고팔기 가장 좋은 시간)

바로가기

 

문제 설명

영문

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.

 

한글

prices[i]가 i번째 날의 주식 가격인 배열 prices가 주어집니다.

 

특정 주식을 구매할 하루를 선택하고 해당 주식을 판매할 미래의 다른 날을 선택 하여 수익을 극대화하려고 합니다 .

이 거래에서 얻을 수 있는 최대 이익을 반환합니다 . 이익을 얻을 수 없으면 0을 반환하십시오.

 

제한조건

• 1 <= prices.length <= 10^5
• 0 <= prices[i] <= 10^4

 

입출력 예

입력	출력
prices = [7,1,5,3,6,4]	5
prices = [7,6,4,3,1]	0

 

 

해답 및 해설

파이썬 (Python)

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

        while r < len(prices):
            profit = prices[r] - prices[l]

            if profit <= 0:
                l = r
            elif profit > max_profit:
                max_profit = profit

            r += 1
        
        return max_profit

투포인터로 푸는 풀이

 

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) == 0:
            return 0
        
        min_price = prices[0]
        max_price = prices[0]
        profit = 0

        for p in prices:
            if p > max_price:
                max_price = p
            elif p < min_price:
                profit = max(profit, max_price - min_price)
                min_price = p
                max_price = p
        profit = max(profit, max_price - min_price)

        return profit

포인트 대신 값을 저장해두는 경우도 있었다. 이 풀이가 더 속도가 빨랐다. 아마 값이 조건문의 조건에 해당하지 않으면 넘어가고, 값을 계속 조회하지 않기 때문으로 보인다.