주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다.
정보 상인은 정보를 사고파는 사람을 의미한다.
호석이는 아직 상인계의 새싹이기 때문에, 초기 투자를 통해서 여러 명의 "정보 고릴라"들로부터 정보를 모으려고 한다.
정보 고릴라란 여기저기서 정보를 수집하는 사람들을 의미한다.
일단 정보를 긁어모으기 위해서 호석이는 여러 정보 고릴라들에게 정보를 구매하려고 한다.
암흑가의 연락망은 뻗어 있기 때문에 누가 어떤 정보를 얻었는지에 대한 찌라시들이 수시로 퍼진다.
찌라시로 알 수 있는 것은, 어떤 이름을 가진 고릴라가 C1, C2, …, Ck 만큼의 가치가 있는 정보 k개를 얻었다는 점이다.
호석이는 이를 바탕으로 임의의 시점에 특정 고릴라에게 정보를 몇 개 살 것인지를 정할 수 있다.
이때 가치 순으로 가장 비싼 정보를 구매한다.
예를 들어 고릴라가 가진 정보가 10개이고, 호석이가 사고 싶은 정보 개수가 4개라면, 고릴라는 10개 중에서 가치 순으로 가장 비싼 4개를 팔 것이다.
한 번 거래한 정보는 호석이에게 더 이상 가치가 없기 때문에 고릴라로 그 정보를 파기한다.
당신은 암흑가의 주역이며 양대 산맥이 될 가능성이 있는 호석이를 주시하고 있다.
관찰하면서 얻은 정보는 총 Q개이다. 각 정보는 다음의 2가지 중 하나이다.
1 Name k C1, C2, …, Ck : 이름이 [Name]인 고릴라가 k개의 정보를 얻었으며, 각 가치는 C1부터 Ck이다.
2 Name b : 호석이가 이름이 [Name]인 고릴라에게 b개의 정보를 구매한다. 이때 고릴라가 가진 정보들 중 가장 비싼 b개를 구매하며, 고릴라가 가진 정보가 b개 이하이면 가진 모든 정보를 구매한다.
결과를 위해서 호석이가 가진 정보들의 가치 총합, 즉 호석이가 정보들을 구매하는 데에 쓴 돈의 총합을 구하자.
입력
고릴라들이 정보를 얻는 사건과 호석이가 거래하는 정보가 시간순으로 주어진다.
첫 번째 줄에는 쿼리의 개수 Q가 주어진다.
이어서 Q개의 줄에 걸쳐서 각 줄에 쿼리가 주어진다. 쿼리는 1이나 2로 시작한다.
1로 시작하는 경우에는 정보를 얻은 정보 고릴라의 이름과 k가 주어지며, 이어서 k개의 정보 가치 C1, …, Ck가 자연수로 주어진다.
모든 Ci는 1 이상 100,000 이하이다.
2로 시작하는 경우에는 호석이가 거래하려는 정보 고릴라의 이름과 구매하려는 정보의 개수 b가 주어진다.
출력
모든 쿼리가 종료되었을 때에 호석이가 얻게 되는 정보 가치의 총합을 출력하라.
반응형
풀이
import sys
import heapq
from collections import deque
input = sys.stdin.readline
Q = int(input().rstrip())
Gorilla = dict()
ans = 0
for _ in range(Q):
tmp = deque(input().rstrip().split())
cur_Q = int(tmp.popleft())
name = tmp.popleft()
if cur_Q == 1:
if name not in Gorilla.keys():
Gorilla[name] = list()
n = int(tmp.popleft())
for value in tmp:
heapq.heappush(Gorilla[name], -int(value))
else:
if name not in Gorilla.keys():
continue
n = int(tmp.popleft())
for _ in range(n):
if len(Gorilla[name]) == 0:
break
ans += -heapq.heappop(Gorilla[name])
print(ans)
728x90
문제가 긴 편인데 요약하자면 1의 경우에는 저장, 2는 출력하라는 말을 길게 써놓은 것이다.
출력 할 때는 가치(숫자)가 높은 순서대로 pop하여 출력하면 된다.
입력값을 원하는대로 재단하기 편하도록 deque자료형을 사용했다.
deque 자료형은 Double-ended queue 로 양쪽 끝에서 자료의 삽입과 삭제가 가능하다.
해당 문제에서는 앞에 나오는 데이터에 따라 name 뒤에 나오는 숫자의 활용이 달라진다.
때문에 앞에 나오는 데이터를 먼저 처리해주었다.
{key1 : list(), key2 : list()} 의 형태로 데이터를 보관하기 위해 이름을 확인하고 해당 key(name)값이 존재하는지 검증하는 과정을 삽입하였다.
1의 경우 즉, 데이터를 추가하는 경우 name에 해당하는 key값이 존재하지 않다면 dictionary에 새로운 key에 대한 공간을 할당했다.
2의 경우 데이터를 추출하는 과정이므로 name에 해당하는 key값이 존재하지 않다면 데이터 또한 존재하지 않기 때문에 해당 루프를 넘기도록 continue 하였다.
데이터를 입출력하는 과정에서는 heapq 라이브러리를 활용하여 최대 힙을 구현하였다.
heapq 라이브러리에서 최대 힙을 따로 제공하지는 않기 때문에 값을 음수로 변환하여 입출력하는 방식으로 최대힙을 구현하였다.
숫자 그대로 입력한다면 숫자가 작은 값이 우선순위이기 때문에 마이너스를 붙혀 추가하면 우선순위를 뒤집을 수 있다.
ex) 3과 7 이 있을 때 3이 우선순위가 높지만 -3과 -7로 변환하면 -7이 우선순위가 높다.
마지막으로 2 (데이터를 추출하는) 과정에서 해당 key에 해당하는 value가 더이상 존재하지 않다면 루프를 중단했다.
코드가 다소 복잡해보일 수 있지만 여러 자료형을 활용했을 뿐 난해한 풀이과정을 아니라고 생각한다.
다른 풀이도 확인해보았는데, 굳이 heapq를 활용하지 않고 리스트 정렬을 통해서 문제를 풀어도 충분히 통과할 수 있는 문제이기는 했다.
