백준 정보 상인 호석(22252)

정보 상인 호석

1. 힌트

1) 코딩테스트 문제 특성상 지문이 깁니다. 이럴땐 예제 입력을 한번 보고 지문을 같이 읽으면 문제를 이해하는데 도움이 됩니다.

2) 고릴라마다 정수를 큰 순으로 저장하는 우선순위 큐를 유지하면 가장 비싼 $b$개를 쉽게 구할 수 있습니다.

3) (이름, 우선순위 큐) Map을 정의하면 고릴라의 이름으로 그 고릴라의 우선순위 큐를 대응시킬 수 있습니다. 예제 입력에서 알 수 있듯이 입력으로 주어지는 $b$가 실제 그 고릴라가 가지고 있는 정보의 개수보다 많을 수 있음에 유의합니다.

2. 접근

1) 우선순위 큐

$Q$의 범위가 엄청 큽니다. 적절한 자료구조를 선택해야합니다.
우리는 2번 연산이 주어졌을 때, 어떤 고릴라가 가지고 있는 가장 비싼 정보 $b$개의 가치의 합을 알고 싶습니다. 또한 그 정보를 사들인 정보는 고릴라가 파기해야하므로 최댓값을 빠르게 구할 수 있고 삭제할 수도 있는 자료형이 필요합니다. 바로 우선순위 큐입니다. 삽입과 삭제를 $O(lgN)$에 할 수 있습니다. $k$개의 원소가 주어지면 $O(klgN)$의 시간이 걸리지만 문제에서 쿼리 전체의 $k$의 합은 $10^6$이하라고 했으므로 충분히 시간 안에 가능합니다.

2) Map

어떤 고릴라의 이름이 정수로 주어지면 좋겠지만 문자열로 주어지기 때문에 배열을 사용해서 우선순위큐 배열을 만들 수가 없습니다. 이럴 때 사용하는 것이 Map입니다. $O(lgN)$에 어떤 원소의 존재 여부를 알 수 있고, 삽입과 삭제도 할 수 있습니다. (이름, 우선순위 큐)로 대응해주는 Map을 정의해줍시다.

3. 구현

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<String, PriorityQueue<Integer>> S = new HashMap<>();
        long sum = 0;
        int Q = Integer.parseInt(br.readLine());
        for (int q = 0; q < Q; q++) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int o = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            if (S.get(name) == null)
            	S.put(name, new PriorityQueue<>(Collections.reverseOrder()));
            PriorityQueue<Integer> pq = S.get(name);
            if (o == 1) {
                int k = Integer.parseInt(st.nextToken());
                for (int i = 0; i < k; i++) 
                    pq.offer(Integer.parseInt(st.nextToken()));
            } else {
                int b = Math.min(pq.size(), Integer.parseInt(st.nextToken()));
                for (int i = 0; i < b; i++) sum += pq.poll();
            }
        }
        System.out.println(sum);
    }

}