[백준/BOJ][Python] 11501번 주식

https://www.acmicpc.net/problem/11501

11501번: 주식

문제

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

1. 주식 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.

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

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

입력

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

출력

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

예제 입력 1 

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

예제 출력 1 

0
10
5

 

아이디어

문제를 처음 읽었을 때 당최 어떻게 구해야 하는 건지 감이 안왔다.

하지만 알고보니 단순하게 1 2 3 이면 Day 1에 사고, Day 2에도 사고 마지막 날에 팔면 된다. 그래서 이익은 마지막 날에 갖고 있던 주식을 모두 파니까 (3-1) + (3-2) = 3이 된다.

반면에 5 4 3이면 갈수록 주가가 떨어지므로 아무것도 안 하면 최대 이익은 0이 될 것이다.

1 1 3 1 2 면  Day 1에 사고  Day 2에 사고  Day 3에는 갖고 있던 주식을 팔아야 이익이 생기니까  Day 3까지의 이익은 (3-1) + (3-1) = 4 이고  Day 4에는 사고 마지막 날에는  Day 4에 산 주식을 팔면 되므로 이익은 2 - 1 = 1 따라서, 이 경우 최대 이익 = 4 + 1 = 5가 될 것이다.

 

이 방식을 토대로 처음부터 순차하는 방식으로 코드를 짰는데 시간초과가 나왔다.

# 시간초과
T = int(input())

price_list = [] # 입력한 주가
temp_list = []
benefit = 0 # 이익
temp = 0
index = 0
hold = 0

for _ in range(T):
    n = int(input())
    price_list = list(map(int, input().split()))

    for i in range(1, len(price_list)):
        if price_list[i-1] <= price_list[i]:
            temp = price_list[i]
            index = i-1
        else:
            for j in range(index+1):
                benefit += temp - price_list[j]
                hold = index+2
    for k in range(hold, index+1):
        benefit += temp - price_list[k]

    if benefit < 0:
        benefit = 0
    print(benefit)
    benefit, temp, hold, index = 0, 0, 0, 0
    price_list.clear()

근데 풀면서도 for문이 너무 중첩돼서 비효율적이라고 생각하긴 했다...

 

Anyway, 내가 다시 푼 방법은 리스트로 만들어서 거꾸로 방문해서 최댓값(처음 최댓값은 리스트에 마지막 값으로 설정)보다 작으면 이익이 생기므로 최댓값에서 빼고, 최댓값보다 큰 숫자가 나오면 최댓값을 바꿔서 다시 이익을 계산하면 된다.

 

코드

T = int(input()) # 케이스 개수

price_list = []
benefit = 0 # 이익

for _ in range(T):
    n = int(input())
    price_list = list(map(int, input().split()))
    max = price_list[n-1] # 처음 최댓값은 리스트의 마지막 값
    
    for i in range(len(price_list)-2, -1, -1): # 뒤에서 2번째 인덱스부터 거꾸로
        if price_list[i] >= max: # max보다 크면 max 값 재설정
            max = price_list[i]
        else: # price_list[i] < max 
            benefit += max - price_list[i] # 이익 계산

    print(benefit)
    # 다른 경우를 계산하기 위해 초기화
    price_list.clear()
    benefit = 0