백준 - 주식 / Silver 2 / 11501번 / Python

문제 📋

백준 - 주식

이상적인 풀이 📝

import sys

T = int(sys.stdin.readline())

for t in range(T):

    N = int(sys.stdin.readline())
    price = list(map(int, sys.stdin.readline().split()))

    money = 0
    maxPrice = 0
    
    for i in range(len(price)-1, -1, -1):
        if price[i] > maxPrice:
            maxPrice = price[i]
        else:
            money += maxPrice - price[i]

    print(money)

날짜 별 주식 가격을 미리 알고 있을 때 최대 이익을 실현하는 문제이다.

쌀 때 주식을 산 뒤 최대 가격일 때 파는 Greedy 문제인데
가장 이상적인 풀이법은 바로 뒤에서부터 탐색하는 것이다.

뒤에서부터 탐색하면서 주식가격이 더 크다면 최댓값을 갱신해주고
더 작다면 최댓값과 현재 가격과의 차이를 이익에 더해주면 된다.

하지만 난 이 아이디어가 시험장에서 논리적으로 쉽게 판단할 수 있는 아이디어라고 생각하지 않는다.
만약에 뒤에서부터 탐색한다는 아이디어가 안 떠오른다면 어떻게 해야 할까?

아이디어를 생각하지 못했을 때의 풀이 📝

import sys


def solution(n, stock_prices):
    day_prices = list(enumerate(stock_prices))
    day_prices.sort(key=lambda x: (-x[1], -x[0]))
    result = 0
    today = 0

    for day, price in day_prices:
        if day > today:
            for i in range(today, day):
                profit = price - stock_prices[i]

                if profit > 0:
                    result += profit
            today = day + 1
    return result


t = int(sys.stdin.readline())
answers = []

for _ in range(t):
    n = int(sys.stdin.readline())
    stock_prices = list(map(int, sys.stdin.readline().split()))
    answers.append(solution(n, stock_prices))

for answer in answers:
    print(answer)

이 코드도 이상적인 풀이보다 느리지만 통과한 코드이다.
먼저 day_prices 리스트에 (가격, 날짜)의 형태로
주식들을 비싼 순으로 정렬해서 저장 해놓았다.

그런 다음 가격이 큰것 부터 하나씩 보면서
타겟 날짜가 현재 날짜보다 미래라면
그때까지 이익을 낼 수 있는 주식들을 전부 구매 후
타겟 날짜 가격으로 모두 판매하고
타겟 날짜로 날짜를 초기화 해주었다.