LeetCode - 121. 주식을 사고 파는 최고의 시간. DSA #3 설명.

Leetcode - 121. 주식 매매의 최적기

쉬운

질문 링크

암호

Python || C++ || TypeScript

먼저 알아야 할 문제는 주식을 한 번 사고 팔아 얻을 수 있는 최대의 이익을 요구하는 것입니다.
그리고 얻을 수 있는 최대 이익은 최대 가격과 최소 가격의 차이입니다.
가격이 최소일 때 가격이 최대일 때 판매하면 최대 이익을 얻습니다.

예를 들어, 가격이 [1, 2, 3, 4, 5]인 경우 주식을 1에 사고 5에 팔면 이익은 4입니다.

마찬가지로 가격이 [7, 1, 5, 3, 6, 4]인 경우 주식을 1에 사고 6에 팔면 이익은 5입니다.

가격이 [7, 6, 4, 3, 1]이면 수익을 낼 수 없습니다.

먼저 무차별 대입 방식에 대해 논의해 보겠습니다.

무차별 접근

우리는 첫날 주식을 산다

우리는 매일 판매하여 얻을 수 있는 모든 이익을 계산합니다. 즉, 2일차에 판매하고 이익을 저장한다는 의미입니다.
우리는 그것을 3일째에 팔고 이익을 저장합니다.

이 두 가지 사항을 하루 종일 반복합니다.

우리가 만들 수 있는 최대 이익을 반환합니다.

두 개의 for 루프를 사용하여 위의 접근 방식을 코딩할 수 있습니다.

암호

def bestTimeForStockMethod1(prices: list[int]) -> int:
    max_profit = 0
    for buy_index, buy_value in enumerate(prices):
        for sell_index in range(buy_index + 1, len(prices)):
            curr_profit = prices[sell_index] - buy_value
            max_profit = max(max_profit, curr_profit)
    return max_profit

예제를 통해 위의 코드를 이해해 봅시다.

prices = [7, 1, 5, 3, 6, 4]
--> 첫 번째 반복

우리는 첫날 주식을 매수합니다. 즉, 주가7로 주식을 매수합니다.

2일차에 주식을 매도합니다. 즉, 주식을 가격1에 매도합니다.

이익은 1 - 7 = -6입니다. 즉, 우리는 손해를 보고 있습니다.

max_profit을 업데이트합니다.

3일째에 주식을 매도합니다. 즉, 주식을 가격5에 매도합니다.

이익은 5 - 7 = -2입니다. 즉, 우리는 손해를 보고 있습니다.

max_profit을 업데이트합니다.

.........계속..................................

6일째에 주식을 매도합니다. 즉, 주식을 가격4에 매도합니다.

이익은 4 - 7 = -3입니다. 즉, 우리는 손해를 보고 있습니다.

max_profit을 업데이트합니다.

--> 두 번째 반복

둘째 날에 주식을 매수합니다. 즉, 가격1으로 주식을 매수합니다.

3일째에 주식을 매도합니다. 즉, 주식을 가격5에 매도합니다.

이익은 5 - 1 = 4입니다.

max_profit을 업데이트합니다.

등등.

결국 우리는 우리가 만들 수 있는 최대 이익을 얻게 될 것입니다.
Time Complexity: O(n^2)Space Complexity: O(1)

더 나은 접근 방식

prices = [7, 1, 5, 3, 6, 4]
위의 접근 방식과 마찬가지로 1일, 즉 가격7에 주식을 매수합시다.

이제 2일차에 주식을 매도하면 1 이익을 얻게 됩니다 1 - 7 = -6-6 . 그게 무슨 이익이냐.. 손실입니다.
그리고 이 손실로부터 우리는 2일째 주식 가격이 1일째 주식 가격보다 낮다고 말할 수 있습니다.
그렇다면 왜 우리는 1일에 주식을 매수합니까? 2일차 즉 가격1에 주식을 매수합시다. 그래서 우리는 움직인다
2일째, 즉 가격1에 대한 포인터입니다.

이제 3일째에 주식을 매도할 때 즉 가격5에 이익5 - 1 = 4을 얻습니다.4 . 우리는 이 이익을 max_profit에 저장합니다.

이제 우리는 주식을 4일째에 가격3에 매도합니다.
우리는 이익을 얻을 것입니다 3 - 1 = 2 . 우리는 최대 이익, 즉 4를 저장할 것입니다.

이제 우리는 주식을 5일째, 즉 가격6에 매도합니다.
우리는 이익을 얻을 것입니다 6 - 1 = 5 . 우리는 최대 이익, 즉 5를 저장할 것입니다.

이제 우리는 주식을 6일째, 즉 가격4에 매도합니다.
우리는 이익을 얻을 것입니다 4 - 1 = 3 . 우리는 최대 이익, 즉 5를 저장할 것입니다.

이제 우리는 루프의 끝에 있으며 어떠한 손실도 발생하지 않았기 때문에 가능한 가장 낮은 가치로 주식을 구입했음을 의미합니다.
따라서 우리가 저장하는 max_profit는 우리가 만들 수 있는 최대 이익입니다.

영어가 적은 다른 예를 들어 보겠습니다.

prices = [7, 2, 5, 6, 1, 4]
두 개의 포인터를 가지자

[7,     2, 5, 6, 1, 4]
 |      |
 Buy    sell

 2 - 7 = -5 
 Loss which means we can buy stock at lower price 
 therefore we move our buy pointer to sell pointer and increase sell pointer by 1

[7, 2,     5, 6, 1, 4]
 |         |
 buy       sell

5 - 2 = 3    max_profit = 3

[7, 2,     5, 6, 1, 4]
    |         |
    buy      sell

6 - 2 = 4    max_profit = 4

[7, 2,  5, 6, 1, 4]
    |         |
    buy      sell

1 - 2 = -1   max_profit = 4

Loss which means we can buy stock at lower price 
therefore we move our buy pointer to sell pointer and increase sell pointer by 1

[7, 2,  5, 6, 1,    4]
              |     |
              buy   sell

4 - 1 = 3    max_profit = 4

we are at the end of the loop. Therefore, we return max_profit i.e 4

Time Complexity: O(n)Space Complexity: O(1)

암호

두 포인터 접근 방식을 사용하여 이를 코딩할 수 있습니다.

def bestTimeForStockMethod2(prices: list[int]) -> int:
    max_profit = 0
    buy, sell = 0, 1
    while sell < len(prices):
        curr_profit = prices[sell] - prices[buy]
        if curr_profit < 0:
            buy = sell
        max_profit = max(max_profit, curr_profit)
        sell += 1
    return max_profit