Baekjoon Training #11501

---

#11501 주식

import sys

input = sys.stdin.readline

n = int(input())    # 몇번의 거래를 진행할지 입력

for _ in range(n):  # 거래 횟수만큼 반복
    days = int(input())     # 몇일동안 거래진행할지 결정
    stock = list(map(int, input().split()))     # 거래일동안 주식가격 리스트
    stock = list(reversed(stock))       # 역순정렬 리스트로 변경
    max_price = stock[0]       # max_price 초기화
    profit = 0      # 총 이익 0으로 초기화
  
    for price in (stock[1:]):   # 0번 인덱스를 max_price로 설정하였으므로 1번 인덱스부터 조사 진행
        if price > max_price:   # 현재 주가가 max_price보다 크면
            max_price = price   # max_price 재설정
        else:                   # 현재 주가가 max_price보다 크면
            profit += max_price - price     # 그 차이를 총이익에 추가

    print(profit)

이번 코드의 핵심은 뒤에서부터 서칭을 하여 최대값보다 작으면 바로 이익 실현하는 발상이다. 처음에는 최대값을 찾아서 그 앞의 값들을 전부 이익 실현을 하고 최대값 이후의 인덱스부터 슬라이싱을 하여 재귀호출하는 방식을 이용하고자 했으나 코드가 난잡해지고 재귀호출 때문에 시간초과를 해결하지 못했다. 그러나 위의 코드처럼 역순으로 판단하고 넘어가버리는 방식을 채택하니 시간초과 문제가 해결되었다.

코드에 대한 설명은 주석으로 했으나 핵심적인 부분인 내부 for문 부분을 살펴보자.  내부 for문은 리스트가 역순정렬 되었으므로 앞에서부터 max_price를 계속 설정해가며 최대값 이하의 값을 만나면 그 차이를 총이익에 추가하는 구조이다.

---