[BOJ22252] 정보 상인 호석 (자료구조, 해쉬맵, 우선 순위 큐)

 

 

---

문제 링크 

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

22252번: 정보 상인 호석

 

문제 풀이

- 해쉬맵, 우선순위 큐 사용하여 풀이

- 결과 최대치 long

 최대치 생각해보기 - 쿼리 10만개가 주어지고, 고릴라가 10만 가치의 정보를 10만개씩 가지고 있고, 구매자가 10만개씩 구매한다면 .. 쿼리가 10만개 있을 때 5만개씩 상점에 정보 추가하고, 5만개씩 상점에서 구매자가 구매한다면 

= 50,000 * 10^5 * 10^5 (int 범위 초과)

- 고릴라 상점을 Map<String, PriorityQueue<Integer>>  자료구조로 나타냄 

- 고릴라 상점의 정보 가치는 내림차순으로 정렬해야 하는데 PriorityQueue의 생성자에 Comparator.reverseOrder() 설정

 

 

절차

Query1의 경우 

- 고릴라명 k C ... : 고릴라가 k개의 정보를 가지고 있고, 가치는 C .. 이다

- 해시맵 초기화와 우선 순위큐(내리차순)  데이터 추가

 

Query2의 경우 

- 고릴라명 b : 고릴라명에 해당하는 상점에서 b개 만큼의 가치가 가장 비싼 자료를 구매한다

- 우선 순위 큐에 저장된 데이터 개수와 구매 개수를 비교하고, 그 수만큼 합산한다.

(데이터가 없는데 pop()하면 NullPointException 출력)

 

제출 코드

import java.util.*;
import java.io.*;

public class Main {
    
    static void process() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int Q = Integer.parseInt(br.readLine());

        Map<String, PriorityQueue<Integer>> storeMap = new HashMap<>();
        long ans = 0L; // 결과 최대치 주의

        while(Q > 0) {
            Q -= 1;

            st = new StringTokenizer(br.readLine());

            int queryNumber = Integer.parseInt(st.nextToken());
            String name = st.nextToken();

            storeMap.putIfAbsent(name, new PriorityQueue<>(Comparator.reverseOrder()));
            PriorityQueue<Integer> storeQue = storeMap.get(name);

            if(queryNumber == 1) {
                int k = Integer.parseInt(st.nextToken());
                for(int i = 1; i <= k; i++) {
                    storeQue.offer(Integer.parseInt(st.nextToken()));
                }
            } else {
                int request = Integer.parseInt(st.nextToken());

                if(storeQue.size() >= request) {
                    while(request > 0) {
                        request -= 1;
                        ans += storeQue.poll();
                    }
                } else {
                    while(!storeQue.isEmpty()) {
                        ans += storeQue.poll();
                    }
                }
            }
        }

        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        bw.write(String.valueOf(ans));
        bw.flush();
        bw.close();
    }

    public static void main(String[] args) throws Exception {
        process();
    }
    
}