백준 22252 - 정보 상인 호석

문제

https://www.acmicpc.net/problem/22252

리뷰

우선순위큐와 해시맵을 사용하여 풀이할 수 있는 문제였다.

주어진 쿼리에 대하여 정보 고릴라들을 표현하기 위해 고릴라 이름
(String)을 키로 하는 HashMap을 이용하였다. 해당 맵은
값으로 정보(Long)를 저장하는 우선순위큐를 가지며, 내림차순으로
값을 정렬하여 가장 큰 값이 우선적으로 poll()되게 구성한다.

해당 자료 구조를 이용하여 1 쿼리가 들어올 경우 맵에 이미 저장된
고릴라인지 확인하고 저장되지 않았을 경우 새로 우선순위큐를 생성해
저장해준다. 그리고 이어지는 해당 고릴라가 가진 값을 힙에 저장한다.

2 쿼리가 들어올 경우 맵에 해당 고릴라가 존재하는지 확인하고,
고릴라가 가진 정보가 $k$개보다 많은 경우엔 $k$개만, 이외 경우엔 모든
정보를 누적된 sum에 더하여 준다.

문제를 풀이하며 유의할 점은 $C$의 최대값이 $100,000$이고 $k$의 최대값도
마찬가지로 $100,000$이므로 정보들의 가치 합이 충분히 int 타입의 최대값을
넘어갈 수 있기 때문에, 이를 적절히 더 큰 타입으로 설정해주어야 한다는 점이었다.

또한, HashMap을 사용하여 고릴라들의 정보를 저장하는 과정에서 containsKey와
같은 메서드를 이용해 저장된 고릴라인지를 확인하면 $O(N)$의 시간복잡도를 띄기
때문에 이를 $O(1)$의 시간복잡도를 띄도록 get을 활용하였다.

로직의 시간복잡도는 쿼리를 처리하는 부분에서 고릴라들의 수를 $N$이라고 가정했을 때
$O(QlogN)$ 형태로 수렴하므로, $Q=100,000$인 최악의 경우에도 무난히 제한 조건
2초를 통과한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

import static java.lang.Integer.parseInt;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        HashMap<String, PriorityQueue<Long>> gorillas = new HashMap<>();
        long sum = 0;

        int Q = parseInt(br.readLine());
        int cmd, k;
        long value;
        String name;
        StringTokenizer st;
        PriorityQueue<Long> pq;

        while (Q-- > 0) {
            st = new StringTokenizer(br.readLine());
            cmd = parseInt(st.nextToken());
            name = st.nextToken();
            k = parseInt(st.nextToken());

            if (cmd == 1) {
                if (gorillas.get(name) == null) {
                    gorillas.put(name, new PriorityQueue<>((l1, l2) -> Long.compare(l2, l1)));
                }

                pq = gorillas.get(name);
                while (k-- > 0) {
                    value = Long.parseLong(st.nextToken());
                    pq.offer(value);
                }

            } else {
                pq = gorillas.get(name);
                if (pq == null) continue;

                if (pq.size() <= k) {
                    while (!pq.isEmpty())
                        sum += pq.poll();
                } else {
                    while (k-- > 0)
                        sum += pq.poll();
                }
            }
        }

        System.out.println(sum);
        br.close();
    }
}

결과