백준 그리디 문제풀이 입니다.
문제
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)
위 풀이가 가장 빠르고 간결한 풀이였습니다.
감사합니다.