[백준] #11501 주식(python)

📌문제

홍준이는 요즘 주식에 빠져있다. 그는 미래를 내다보는 눈이 뛰어나, 날 별로 주가를 예상하고 언제나 그게 맞아떨어진다. 매일 그는 아래 세 가지 중 한 행동을 한다.

주식 하나를 산다.
원하는 만큼 가지고 있는 주식을 판다.
아무것도 안한다.
홍준이는 미래를 예상하는 뛰어난 안목을 가졌지만, 어떻게 해야 자신이 최대 이익을 얻을 수 있는지 모른다. 따라서 당신에게 날 별로 주식의 가격을 알려주었을 때, 최대 이익이 얼마나 되는지 계산을 해달라고 부탁했다.

예를 들어 날 수가 3일이고 날 별로 주가가 10, 7, 6일 때, 주가가 계속 감소하므로 최대 이익은 0이 된다. 그러나 만약 날 별로 주가가 3, 5, 9일 때는 처음 두 날에 주식을 하나씩 사고, 마지막날 다 팔아 버리면 이익이 10이 된다.

입력

입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다.

출력

각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.

예제 입력

3
3
10 7 6
3
3 5 9
5
1 1 3 1 2

예제 출력

0
10
5

백준 11501번 문제

💡Idea

홍준이가 부자💸가 될 수 있도록 도와주는 문제입니다.

처음에는 아래와 같은 방식으로 문제를 해결하고자 했습니다.

1. 다음 날의 주식의 값이 오늘의 주식의 값보다 비싸다면 주식을 산다.
2. 다음 날의 주식의 값이 오늘의 주식의 값보다 싸다면 주식을 판다.

하지만 이렇게 문제를 해결하려고 하면 다음과 같은 상황에서 답을 제대로 찾을 수가 없습니다.

2 1 3 1 3

이 입력인 경우, 첫째날과 둘째날에 주식을 사고, 셋째날에 산 주식 두 개를 다 팔아야 최대 이익을 얻을 수 있다.
하지만 위와 같은 방식을 적용할 경우 첫째날에 주식을 사지 않으니 최대 이익을 구할 수 없다.

📍 최대 이익을 얻기 위해서는 주식의 최고점이 나올 때까지 주식을 샀다가, 최고점이 나오면 팔고, 다시 최고점이 나올 때까지 샀다가 최고점이 나오면 팔고 하는 과정을 반복해야 합니다.

그러기 위해서는 max와 배열 slice를 사용해서 계속해서 최고점을 찾아가는 방법을 사용할 수도 있지만, 뒤에서부터 주식 값을 확인해나가면 $O(N)$으로 문제를 해결할 수 있어 시간복잡도를 훨씬 줄일 수 있습니다.

1. 현재 값이 주식 최고 가격보다 작은 경우 : 해당 가격으로 주식을 사고 주식 최고 가격으로 주식을 팔면 된다.
   ➡ 현재 이익 값에 (주식 최고 가격 - 현재 주식 가격)을 더해준다.
2. 현재 값이 주식 최고 가격보다 큰 경우 : 주식 최고 가격을 현재 값으로 갱신해준다.
3. 현재 값이 주식 최고 가격과 동일한 경우 : 아무 이득도 얻을 수 없으니 아무 일도 하지 않는다.

💻코드

• ⏰ 시간 : 3524 ms / 메모리 : 173228 KB

import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
    N = int(input())
    prices = list(map(int, input().split()))
    cur_max = prices[-1]
    m = 0
    for i in range(N - 2, -1, -1):
        if prices[i] > cur_max:
            cur_max = prices[i]
        elif prices[i] < cur_max:
            m += (cur_max - prices[i])
    print(m)