Best Time to Buy and Sell Stock

Q: 가장 높은 가격에서 가장 낮은 가격을 빼면 안 되나요?

가장 낮은 가격은 가장 높은 가격 뒤에 올 수 있으며, 매도하기 전에 매수해야 합니다. [7, 2, 5, 9, 1, 4] 에서 1은 9 뒤에 나오므로, 허용되는 최선의 거래는 2에 매수하고 9에 매도하여 7의 이익을 얻는 것입니다.

쉬움그리디

+10

prices 목록이 주어집니다. 여기서 prices[i]는 i일의 주식 한 주 가격입니다. 하루에 한 주를 매수하고 그 이후의 날에 매도할 수 있습니다. 얻을 수 있는 최대 이익을 반환하세요. 가능한 모든 거래에서 손실이 발생한다면 0을 반환하세요.

함수

maxProfit(prices: integer-array) → integer

pricesinteger-array: 각 날짜의 주가를 순서대로
반환값integer: 한 번 매수한 후 나중에 매도하여 얻을 수 있는 최대 이익 또는 0

제약 조건

1 ≤ prices.length ≤ 10⁵
0 ≤ prices[i] ≤ 10⁴
최대 한 번만 거래하며, 매수한 날보다 나중에 매도합니다.

예제

입력: prices = [7, 2, 5, 9, 1, 4]
출력: 7
설명: 1일 차에 2에 사서 3일 차에 9에 팔면 7의 수익을 얻습니다. 가장 저렴한 가격인 4일 차의 1은 9 이후에 나오므로, 그 이후에 가장 잘 팔아도 수익은 3에 불과합니다.

후속 질문

원하는 만큼 거래할 수 있지만, 한 번에 최대 한 주만 보유할 수 있다면 어떨까요?

풀이

매도하기 전에 매수해야 하므로, 답은 최고 가격에서 최저 가격을 뺀 값이 아닙니다. 매도할 수 있는 각 날짜에 대해 가장 좋은 매수 시점은 그보다 앞선 날짜 중 가격이 가장 낮은 날입니다. 날짜를 차례로 살펴보면서 그 최저 가격을 기록해 두면 문제를 한 번만 훑어서 해결할 수 있습니다.

모든 매수 및 매도 쌍을 시도해 보세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

모든 거래는 매수일과 그 이후의 매도일로 이루어지므로, 모든 쌍을 확인하고 가장 큰 차이를 유지하세요. 최선의 이익을 0에서 시작하면 거래하지 않는 선택도 포함됩니다. 가능한 모든 거래를 확인하므로 정답이 맞습니다.

가격이 n개인 목록에는 약 n²/2개의 쌍이 있습니다. 100,000일이면 뺄셈을 약 50억 번 해야 합니다.

알고리즘

best를 0으로 설정합니다.
모든 매수일 buy을 순회합니다.
각 매수일에 대해 그 이후의 모든 매도일 sell을 순회합니다.
prices[sell]에서 prices[buy]를 빼고, 그 값이 더 크면 best에 저장합니다.
best를 반환합니다.

def maxProfit(prices):
    best = 0
    n = len(prices)
    for buy in range(n):
        for sell in range(buy + 1, n):
            best = max(best, prices[sell] - prices[buy])
    return best

지금까지의 최저 가격으로 한 번 순회

핵심 아이디어

판매일 i를 고정합니다. 매수하기 가장 좋은 날은 i일까지 가장 저렴한 날이므로, i일에 끝나는 최선의 거래에서 얻는 수익은 prices[i]에서 지금까지의 최저 가격을 뺀 값입니다. 각 판매일은 그날에 가장 적합한 매수일과 짝을 이루므로, 이러한 수익 중 가장 큰 값이 정답입니다. 새로운 최저가를 기록하는 날의 수익은 거래하지 않는 것과 마찬가지로 0입니다.

이 순회는 각 가격을 한 번씩 읽고 lowest와 best 두 숫자만 유지합니다. 시간 복잡도는 O(n), 공간 복잡도는 O(1)입니다.

알고리즘

lowest를 첫 번째 가격으로 설정하고 best를 0으로 설정합니다.
가격을 순서대로 살펴봅니다.
현재 가격이 lowest보다 낮으면, 현재 가격을 새로운 lowest로 설정합니다.
현재 가격에서 lowest를 뺀 값을 계산하고, 그 값이 더 크면 best에 저장합니다.
best를 반환합니다.

def maxProfit(prices):
    lowest = prices[0]
    best = 0
    for price in prices:
        if price < lowest:
            lowest = price
        elif price - lowest > best:
            best = price - lowest
    return best

함정과 경계 사례

최고 가격에서 최저 가격을 빼서 반환하는 것. [7, 2, 5, 9, 1, 4]에서는 8이 나오지만, 1은 9 뒤에 있습니다. 정답은 7입니다.
정답이 음수가 되도록 하는 것. [9, 7, 4, 3, 1]에서 가장 큰 차이는 -1입니다. best를 첫 번째 차이가 아니라 0으로 시작하세요.
lowest를 0으로 시작하는 것. 그러면 모든 이익이 가격 자체와 같아지므로 [9, 7, 4, 3, 1]은 9를 반환합니다. 첫 번째 가격으로 시작하세요.

자주 묻는 질문3

Best Time to Buy and Sell Stock의 시간 복잡도는 얼마인가요?

한 번 순회하는 해결 방법은 n일 동안 O(n) 시간이 걸립니다. 각 가격을 한 번씩 읽기 때문입니다. 추가 공간은 O(1)입니다. 지금까지의 최저 가격과 최대 이익만 저장하면 됩니다. 모든 날짜 쌍을 시도하면 O(n²) 시간이 걸립니다.

가장 높은 가격에서 가장 낮은 가격을 빼면 안 되나요?

가장 낮은 가격은 가장 높은 가격 뒤에 올 수 있으며, 매도하기 전에 매수해야 합니다. [7, 2, 5, 9, 1, 4]에서 1은 9 뒤에 나오므로, 허용되는 최선의 거래는 2에 매수하고 9에 매도하여 7의 이익을 얻는 것입니다.

Best Time to Buy and Sell Stock는 동적 프로그래밍 문제인가요?

어느 방식으로든 이해할 수 있습니다. 지금까지의 최저 가격은 매일 갱신하는 작은 상태이며, 이것이 동적 프로그래밍 관점입니다. 각 매도를 이전 날짜 중 가장 저렴한 날과 짝짓는 것은 그리디 관점입니다. 두 관점 모두 한 번만 순회하는 동일한 코드로 이어집니다.

def maxProfit(prices):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

인자

prices = [7, 2, 5, 9, 1, 4]

예상 출력