백준 그리디 문제풀이 입니다.

문제

https://www.acmicpc.net/problem/11501

[나의 풀이1]

T = int(input())

stocks = []

for i in range(T):
    N = int(input())
    stocks.append(list(map(int, input().split(" "))))

for i in range(T):
    buy = []
    ans = 0
    # sorted_stock = stocks[i].sort()
    for j in range(len(stocks[i])):
        if stocks[i][j] < max(stocks[i][j:]):
            buy.append(stocks[i][j])
        else:
            ans += sum(list(map(lambda x: max(stocks[i][j:])-x, buy)))
            buy = []
    print(ans)

일별 주식가격을 순회하며 이후 인덱스에 최댓값이 있기 전까지 구매 후 최댓값에 도달할때
판매하는 방식의 풀이입니다. 하지만 위 풀이로 제출했을 시에 2중 for문 안에 max()함수로 N 시간복잡도가 필요하여 시간초과가 났습니다. 그리하여 아래와 같이

[나의 풀이2]

T = int(input())

for i in range(T):
    N = int(input())
    stock = list(map(int, input().split()))

    buy = []
    ans = 0
    sorted_stock = sorted(stock)
    for x in stock:
        if x < sorted_stock[-1]:
            buy.append(x)
            sorted_stock.remove(x)
        else:
            ans += sum(sorted_stock[-1]-k for k in buy)
            sorted_stock.pop()
            buy = []
    print(ans)

최대값을 저장하기 위해 sorted(stock)를 저장해두고 -1 인덱스의 값을 기준으로 판매하는 방식으로 바꾸어보았습니다. 하지만 이 또한 2중 for문 안에 remove()함수로 다시 N 시간복잡도가 발생하여 어려움이 있었습니다. 그리하여 멘토님의 도움을 받아 아래와 같이 값들의 갯수를 저장하는 방식으로 해결할 수 있었습니다.🦋🦋🦋

[다른사람의 풀이1(멘토님)]

import sys
input = sys.stdin.readline

t= int(input())
from collections import Counter
for _ in range(t):
    k = int(input())
    tmpList = input().split()
    tmpList = list(map(int, tmpList))
    dic = dict(Counter(tmpList))
    sortedDic = dict(sorted(dic.items(), key=lambda x: x[0]))
    keysList = list(sortedDic.keys())
    maxN = keysList[-1]
    answer = 0
    tmp = []
    for i in tmpList:
        if i == maxN:
            sortedDic[maxN] -= 1
            if sortedDic[maxN] == 0:
                answer += sum(maxN - k for k in tmp)
                keysList.pop()
                try:
                    maxN = keysList[-1]
                except:
                    break
                tmp = []
            if len(keysList) == 1:
                break
        else:
            sortedDic[i] -= 1
            if sortedDic[i] == 0:
                keysList.remove(i)
            tmp.append(i)
    print(answer)

dict(Counter()) 함수를 사용하여 주식가격별 갯수를 dict형태로 만들어준 풀이입니다.

이 외에 풀이로 인덱스를 반대로 돌면서 이전 주식 가격이 더 싸다면 바로 판매하고 더 비싸다면 최대값을 갱신하는 방식의 풀이 또한 볼 수 있었습니다.🐳🐳🐳

[다른사람의 풀이2]

for _ in range(int(input())):
    n = int(input())
    data = list(map(int,input().split()))
    answer = 0 
    mx = data[-1]
    for i in range(n-2,-1,-1):
        if data[i] > mx: #오늘 가격이 mx라면 
            mx = data[i]
        else:
            answer += mx-data[i] #오늘 가격이 최대가 아니라면 최대-지금가격만큼 더한다 
    print(answer)

위 풀이가 가장 빠르고 간결한 풀이였습니다.

감사합니다.