[백준] 22252 - 정보 상인 호석

1. 문제

22252번: 정보 상인 호석

2. 개요

호석이와 정보 고릴라가 있다.

정보의 수 N과 N개의 줄에 쿼리가 하나씩 주어진다.

쿼리의 종류는 두 가지로

• 1 Name C1, C2, …, Ck : 이름이 Name인 고릴라가 k 개의 정보를 얻었으며, 각 가치는 C1 부터 Ck 이다.
• 2 Name b : 호석이가 이름이 Name인 고릴라에게 b 개의 정보를 구매한다. 이때 고릴라가 가진 정보들 중 가장 비싼 b 개를 구매하며, 고릴라가 가진 정보가 b개 이하이면 가진 모든 정보를 구매한다.

이 때, 호석이가 구매한 정보의 총 가치를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

정보 고릴라와 그의 정보를 관리한다.

정보 고릴라의 이름을 Key, 그 정보를 Value로 하는 딕셔너리를 만드는데, 정보를 구매할 때 가장 비싼 정보를 우선해서 사야하므로 Value를 우선순위 큐로 만들어준다.

쿼리가 1로 시작한다면 모든 정보들을 해당 정보 고릴라의 우선순위 큐에 넣어준다.

2로 시작한다면 먼저 해당 정보 고릴라가 존재하는지 여부를 판단한다.

존재한다면 구입할 정보의 개수와 정보 고릴라의 정보 갯수를 비교한다.

구입할 정보의 개수가 많다면 모든 정보의 가치를 답에 더해주고 우선순위 큐를 비운다.

구입할 정보의 개수가 더 적다면, 해당 갯수만큼 우선순위큐에서 빼 가며 답에 더해준다.

모든 쿼리를 탐색했다면 답을 출력한다.

3-2. Python

import sys
import heapq

N = int(sys.stdin.readline())
answer = 0
gorillas = dict()

for i in range(N):
    query = list((sys.stdin.readline().split()))

    if query[0] == '1':
        if query[1] not in gorillas:
            gorillas[query[1]] = []

        for info in query[3:]:
            heapq.heappush(gorillas[query[1]], -int(info))

    else:
        if query[1] not in gorillas:
            continue

        if int(query[2]) > len(gorillas[query[1]]):
            answer += sum(gorillas[query[1]]) * -1
            gorillas[query[1]].clear()

        else:
            for i in range(int(query[2])):
                answer += heapq.heappop(gorillas[query[1]]) * -1

print(answer)

3-3. C#

답이 int형 범위를 초과하는 경우가 있다.

namespace boj_22252
{
    internal class Program
    {
        static void Main(string[] args)
        {
            int N = int.Parse(Console.ReadLine());
            long answer = 0;

            Dictionary<string, PriorityQueue<int, int>> gorillas = new Dictionary<string, PriorityQueue<int, int>>();

            for (int i = 0; i < N; i++)
            {
                string[] query = Console.ReadLine().Split();

                if (query[0] == "1")
                {
                    if (gorillas.ContainsKey(query[1]) == false)
                    {
                        gorillas[query[1]] = new PriorityQueue<int, int>();
                    }

                    for (int j = 3; j < 3 + int.Parse(query[2]); j++)
                        gorillas[query[1]].Enqueue(int.Parse(query[j]), int.Parse(query[j]) * -1);
                }

                else
                {
                    if (gorillas.ContainsKey(query[1]) == false)
                        continue;

                    if (int.Parse(query[2]) > gorillas[query[1]].Count)
                    {
                        while (gorillas[query[1]].Count > 0)
                        {
                            answer += gorillas[query[1]].Dequeue();
                        }
                    }

                    else
                    {
                        for (int j = 0; j < int.Parse(query[2]); j++)
                        {
                            answer += gorillas[query[1]].Dequeue();
                        }
                    }
                }
            }

            Console.WriteLine(answer);
        }
    }
}