백준 파이썬 11501 : 주식 풀이 (시간초과 해결)

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

11501번: 주식

미래의 가격을 알고 있고, 매일 한 주를 사거나 팔 수 있고, 아무것도 하지 않을 수 있다. 이때의 최대 이익을 구해야 한다.

주식은 싸게 사서 그보다 비싸게 팔면 되는 '매우 간단한' 게임이므로

1. 현재 가격이 미래 가격보다 싸면 사고 

2. 미래 가격보다 비싸면 아무것도 하지 않고 

3. 지금 가격이 최대 가격이면 팔면 된다

 

따라서 

1. 현재 이후의 가격의 최대값을 구하고 

2. 현재 가격이 최대값보다 싸면 사고 

3. 최대값이 됐을 때 팔면 된다 

 

처음에 나는 인덱스 i에 대하여 i 이후의 최대값을 구하고, 현재 가격이 이보다 낮을시 매수하는 식으로 코드를 짰는데 시간 초과가 나왔다. 계속해서 리스트 전체를 조회하여 최대값을 찾아야하므로 시간 초과가 날 수밖에 없다. 

게다가 생각나는대로 바로바로 짜다보니 코드도 꽤 더럽다. 추하게 sys.stdin.readline까지 이용해봤지만 역시나 시간 초과였다. 

 

질문 검색에서 볼 수 있듯, 리스트의 뒤부터 조회하면 시간 초과를 해결할 수 있다 

1. 최대값을 우선 data[-1]로 잡아두고 

2. 인덱스 i의 범위를 range(n-2,-1,-1)로 잡은 뒤에 

    1. data[i]가 최대값보다 크다면 최대값을 갱신하고 

    2. data[i]가 최대값보다 작다면 최대값에서 현재 가격을 뺀만큼을 답에 저장해준다 

#시간 초과가 나는 답 
'''for _ in range(int(input())):
    n = int(input())
    data = list(map(int,input().split()))
    answer = 0 #손익 계산 
    stock = 0 #주식 개수 
    for i,price in enumerate(data):
        if i == 0:
            if price<max(data):
                answer -= price
                stock += 1 
        else:
            right = max(data[i:])
            if price<right: #매수 
                answer -= price
                stock += 1 
            elif price == right: #매도 
                answer += price*stock 
                stock = 0 
    print(answer)'''

#시간 초과 해결 
for _ in range(int(input())):
    n = int(input())
    data = list(map(int,input().split()))
    answer = 0 
    mx = data[-1]
    for i in range(n-2,-1,-1):
        if data[i] > mx: #오늘 가격이 mx라면 
            mx = data[i]
        else:
            answer += mx-data[i] #오늘 가격이 최대가 아니라면 최대-지금가격만큼 더한다 
    print(answer)