BOJ 11501 - 주식

문제 링크

차트 정보가 주어질때 팔아야 할 시점을 계산하고, 다음 판매 시점의 가격보다 낮은 가격이면 하나씩 사모으다가
팔아야 할 시점이 되면 판다.

팔아야 할 시점을 계산하는 방법은 다음과 같다.

1) 차트에서 최고점을 찾고, 가장 늦은 시점의 최고점 index가 판매 시점이다.
2) 1)에서 찾은 판매시점 이후의 차트를 기준으로 1)을 반복한다.
 * 이때 최고점 이후 주가가 내리막이면 내리막인 구간은 체크할 필요가 없기 때문에 skip해야 한다.
   예를 들어 100만 ~ 1 까지 내림차순으로 차트가 주어질 때는 어떻게 해도 수익을 얻을 수 없다.
   내리막 구간을 Skip하면 O(N)으로 확인이 가능하지만, 내리막 구간을 SKIP하지 않으면
   [100만 ~ 1],[999999 ~ 1], ... [2,1] 전부 확인하게 되어 O(N^2)이 된다.   

from collections import deque
import sys


def read():
    return sys.stdin.readline().rstrip()

# 팔아야 할 시점 계산
def get_sell_time(chart):
    time = deque()
    start = 0
    while start < len(chart):
        high = max(chart[start:])
        for i in range(len(chart)-1, -1, -1):
            if chart[i] == high:
                time.append(i)
                start = i+1
                break

        while start < len(chart)-1 and chart[start] > chart[start+1]:
            start += 1
    return time


def solution(chart):
    sell = get_sell_time(chart)
    stock = 0
    expense = 0  # 지출
    profit = 0  # 수입

    for i in range(len(chart)):
        price = chart[i]
        # 팔아야 할 때
        if i == sell[0]:
            profit += stock*price
            stock = 0
            sell.popleft()
            if len(sell) == 0:
                break
            continue
        # 사야 할 때
        if price < chart[sell[0]]:
            expense += price
            stock += 1

    return profit-expense


T = int(read())

for _ in range(T):
    N = int(read())
    chart = list(map(int, read().split()))
    print(solution(chart))