[SWEA] 1859. 백만 장자 프로젝트

https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

요구사항

• 10개의 테스트 케이스 합쳐서 파이썬의 경우 30초
  • 무슨 말인지...
• 힙, 정적 메모리 합쳐서 256MB이내
• 최대이익을 구하자

설계

stack을 사용해서 잘 빼주면서 더하면 된다.

• 리스트에 가격들을 집어 넣는다. 
  • [10, 7, 6] 
• for 문을 리스트의 거꾸로 돌린다.
  • 마지막부터 비교해야 언제 팔지 알지 ! 
  • 3일 째 6원이고 2일 째 7원이다. 그러면 3일 째 오히려 떨어지니 주식 사겠냐 !!
• for price in reversed(stack):    # 거꾸로 돌리기
  • if max_price < price:       #  최대 가격 < 이전 일차 가격  
    • max_price = price   # 이전 일차 가격을 최대 가격으로 만들어준다.
  • else:
    • total_price += max_price - price  # 더하면 되지 

구현

import sys
input = lambda: sys.stdin.readline().rstrip()

t = int(input())

for i in range(t):
    days = int(input())
    stack = list(map(int, input().split()))

    max_price = 0
    total_price = 0

    for price in reversed(stack):
        if max_price < price:
            max_price = price
        else:
            total_price += max_price - price
    
    print(f"#{i + 1} {total_price}")