[softeer] [21년 재직자 대회 본선] 트럭 (python)

https://softeer.ai/practice/info.do?idx=1&eid=631&sw_prbl_sbms_sn=82669 

Softeer

---

문제 회고

처음엔 돈 범위만큼 배열을 만들어 각각의 이익을 얻으려면 필요한 size를 모두 넣어서 구하려고 했다.

지금 생각해보면 매우 무식한 방법이고 시간 초과가 뻔했다.

인터넷 검색을 좀 해봐서 각각의 buyer가 제시한 사이즈에 맞는 금액과 시나리오를 정렬을 하면 가장 사이즈부터 시나리오에 부합하는지 찾기 때문에 더 빠르게 답을 찾을 수 있었다.

만약 해당 buyer가 이전에 이미 지불한 금액이 있었다면 그 금액과 비교해서 더 큰 금액일 시 바꿔주는 부분도 필요했다.

그리고 처음 정렬을 해주었기 때문에 나중에 다시 input으로 받을 때의 순서로 돌리기 위해서 index를 저장하는 것이 중요했다.

---

import sys

n = int(sys.stdin.readline())
offer = []
for i in range(n):
    tmp = list(map(int, sys.stdin.readline().split()))
    for j in range(1, len(tmp), 2):
        offer.append([tmp[j], tmp[j + 1], i + 1])
m = int(sys.stdin.readline())
tmp = list(map(int, sys.stdin.readline().split()))
scenarioes = []
for i in range(m):
    scenarioes.append([tmp[i], i + 1])

offer.sort()
scenarioes.sort()

total = 0
prev_pay = [0] * (n + 1)
s_index = 0
for i in range(len(offer)):
    size, payment, buyer = offer[i][0], offer[i][1], offer[i][2]
    if payment > prev_pay[buyer]:
        total += payment - prev_pay[buyer]
        prev_pay[buyer] = payment
    while s_index < len(scenarioes) and scenarioes[s_index][0] <= total:
        scenarioes[s_index].append(size)
        s_index += 1

scenarioes.sort(key=lambda x: x[1])
for i in scenarioes:
    if len(i) <= 2:
        print(-1, end=' ')
    else:
        print(i[2], end=' ')