문제

문제 접근

문제 해석부터 하면 미래에 가격도 알고 있다는 전제하에 순이익이 최대로 될때 순이익을 구하는 문제다.

가격이 들어있는 배열에 최대값을 찾고 앞에서 부터 최대값을 만나기 전까지 이익 변수에 최대값 - 현재 값 을 해주면서 선형적으로 계산을 해주고 해당 계산이 끝나면 pop를 해줘 쭉쭉 나가는 느낌으로 시도를 했다.

문제 풀이

1트

import sys

sys.stdin = open("input/1859_input.txt")

from collections import deque

t = int(input())

for i in range(t):
    day = int(input())
    arr = deque(list(map(int, input().split())))

    benefit = 0
    cnt = 1
   
    while arr:
        if arr[0] < max(arr):
            benefit +=  (max(arr) - arr[0])
            arr.popleft()  
            
        if max(arr) == arr[0]:
            arr.popleft()    
            
    print(f"#{i+1} {benefit}")

이렇게 했는데 시간초과가 떴다.
내가 푼 알고리즘 시간 복잡도는 O(n^2)
입력이 1,000,000이 최대고 시간 제한은 파이썬은 30초니까
n^2 1초당 10,000(1만)
30초니까 300,000(30만)이 맥스 값이니까 시간초과가 뜨는게 당연했다.

2트(최종 코드)

아무리 생각해도 모르겠어서 구글링을 해보니 마지막 부터 접근하라고 했다.

왜 마지막부터 접근해야 되나 생각을 계속 해봤는데,
선형적으로 접근하면 결과적으로 마지막 이전 값이 마지막 값이랑 계산 되므로 마지막 값을 max값으로 잡고 계산하고 거꾸로 접근 하면서 마지막 값보다 이전 값이 크면 해당값을 max 값으로 변경 시켜주면서 연산을 조금이나마 줄이는 거 같다.

import sys

sys.stdin = open("input/1859_input.txt")

t = int(input())

for i in range(t):
    n = int(input())
    arr = list(map(int, input().split()))
    maxprice = 0
    ret = 0
    
    for j in arr[::-1]:
        if j >= maxprice:
            maxprice = j
            
        else:
            ret += (maxprice - j)
    print(f"#{i+1} {ret}")