이번 문제는 그리디 알고리즘을 이용하여 주식 가격 배열을 뒤에서부터 비교하며 반복마다 가장 큰 가격보다 작을 경우 이익에 현재 가장 큰 가격에서 현재 가격을 뺀 금액을 더해주고, 만약 가장 큰 가격보다 현재 가격이 더 크다면 가장 큰 가격을 갱신해주는 방식으로 해결하였다.

처음에는 문제에서 주어진 그대로 코드가 돌아가도록 작성하였는데 시간초과가 발생하였다. 아무래도 for문 안에서 if문에 max()함수를 사용하여 시간 복잡도가 O(n^2)가 되어 시간초과가 발생한 것으로 예상됐다. 우선 초기에 작성했던 코드이다. cost 뒤에 0을 추가한 이유는 기존 cost의 마지막 원소까지 확인하기 위함이었다.

t=int(input())
for i in range(t):
    n=int(input())
    cost=list(map(int, input().split()))
    cost.append(0)
    use=0
    cnt=0
    profit=0
    for j in range(n):
        if cost[j]<max(cost[j:]):
            use+=cost[j]
            cnt+=1
        elif cost[j]==max(cost[j:]):
            profit+=((cost[j]*cnt)-use)
            cnt=0
            use=0
    print(profit)

새로운 방법을 생각하던 중 max(cost[j:]) 부분이 현재 위치보다 뒤에 있는 수들끼리만을 비교한 다는 것을 이용하여 cost배열을 뒤에서부터 비교하여 max()함수 사용을 없애면 시간 복잡도를 O(n)으로 개선할 수 있겠다는 생각이 들었다.

• t를 입력받는다.
• t번 반복하는 for문을 돌린다.
• n을 입력받는다.
• 주식 가격 배열 cost를 선언하고 입력받는다.
• 총 이익을 저장할 변수 profit을 0으로 정의한다.
• 가장 비싼 가격을 저장하는 변수 mx를 cost[-1]로 정의한다.
• n-2부터 -1까지 1씩 감소하며 반복하는 j에 대한 for문을 돌린다.
  -> 만약 cost[j]가 mx보다 크다면 mx를 cost[j]로 갱신시킨다.
  -> 그 외의 경우에는 profit에 mx-cost[j]를 더한다.
• profit을 출력한다.

Code

t=int(input())
for i in range(t):
    n=int(input())
    cost=list(map(int, input().split()))
    profit=0
    mx=cost[-1]
    for j in range(n-2, -1, -1):
        if cost[j]>mx:
            mx=cost[j]
        else:
            profit+=(mx-cost[j])
    print(profit)