[Easy] 주식을 팔아 최대 이익을 얻는 날 구하기 - 121. Best Time to Buy and Sell Stock

주어진 배열 prices에서 prices[i]는 i번째 날의 주식 가격을 나타냅니다. 한 주식을 사는 날을 선택하고, 이후에 그 주식을 파는 다른 날을 선택하여 최대 이익을 얻고자 합니다. 이 거래에서 얻을 수 있는 최대 이익을 반환하십시오. 이익을 얻을 수 없는 경우 0을 반환하십시오.

 

예제 1:

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

출력: 5

설명: 2번째 날에 가격이 1일 때 사서 5번째 날에 가격이 6일 때 팔면, 이익은 6 - 1 = 5입니다.

주의: 2번째 날에 사고 1번째 날에 파는 것은 허용되지 않습니다. 구매는 판매 이전에 이루어져야 합니다.

 

예제 2:

입력: prices = [7,6,4,3,1]

출력: 0

설명: 이 경우에는 거래가 이루어지지 않으므로 최대 이익은 0입니다.

제약 사항:

• 1 <= prices.length <= 105
• 0 <= prices[i] <= 104

 

풀이

 

주식 가격이 가장 낮은 날을 찾아 그 이후의 최대 이익을 계산해야 합니다. 이 방법을 통해 O(n) 시간 복잡도로 문제를 해결할 수 있습니다. 다음은 파이썬(Python) 코드로 문제를 해결하는 방법입니다:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for price in prices:
            if min_price > price:
                min_price = price
            if max_profit < price - min_price:
                max_profit = price - min_price
        return max_profit

 

min_price: 현재까지의 최저 주식 가격을 추적하기 위해 사용됩니다.

max_profit: 현재까지 얻을 수 있는 최대 이익을 추적하기 위해 사용됩니다.

배열을 순회하면서:

• 주식 가격이 min_price보다 낮으면, min_price를 업데이트합니다.
• 그렇지 않으면, 현재 가격에서 min_price를 뺀 값이 max_profit보다 크면, max_profit을 업데이트합니다.

모든 주식 가격을 확인한 후, 최대 이익을 반환합니다.

 

이 알고리즘은 단일 패스로 배열을 순회하므로 시간 복잡도는 O(n)이며, 공간 복잡도는 O(1)입니다.