[백준]22252:🕵️‍♂️ 정보 상인 호석 - JAVA

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

22252번: 정보 상인 호석

풀이

🪑 우선순위큐, 해쉬맵을 활용한 자료구조 문제이다.

 

📝 문제의 조건들을 정리해 보자.

• 가치 순으로 가장 비싼 정보들을 구매한다.
• 한번 거래한 정보는 파기된다.
• 1로 시작하는 쿼리는 정보를 얻은 고릴라와 가지고 있는 정보 가치를 의미한다.
• 2로 시작하는 쿼리는 거래할 고릴라와 구매하려는 정보의 개수를 의미한다.
• 정보는 시간 순서대로 주어진다.

 

 

🤔 처음에는 문제가 잘 이해가 되질 않아 예제를 보며 따라가 보았다. 예제를 보니, 문제가 한 번에 이해되었다!

1 Cpp 5 10 4 2 8 4 -> CPP고릴라가 5개의 정보를 가지고 있으며 각각의 가치를 의미한다.
1 Java 2 8 2 -> JAVA고릴라가 2개의 정보를 가지고 있으며 각각의 가치를 의미한다.
2 Cpp 2 -> CPP고릴라에게 2개의 정보를 사겠다. 이때 비싼 순서대로 사겠다.
1 Cpp 2 10 3 -> CPP고릴라가 2개의 정보를 추가로 얻었다.
2 Cpp 3 -> CPP고릴라에게 3개의 정보를 사겠다.
2 Java 1 -> JAVA고릴라에게 1개의 정보를 사겠다.
2 Python 10 -> PYTHON고릴라에게 10개의 정보를 사겠다.

📌 한 줄씩 따라가 보자!

1. CPP고릴라가 가진 정보를 가치 순서대로 내림차순 하면 10, 8, 4, 4, 2가 된다.
2. JAVA고릴라가 가진 정보를 가치 순서대로 내침하순하면 8, 2가 된다.
3. CPP고릴라에게 2개의 정보를 사면 가장 큰 가치를 지닌 18(10 + 8)을 사게 되며 정보를 산 후 CPP고릴라의 상태는 4, 4, 2가 된다. 
4. CPP고릴라가 두개의 추가 정보를 얻는다. CPP고릴라의 상태는 10, 4, 4, 3, 2가 된다.
5. CPP고릴라에게 3개의 정보를 산다. 가장 큰 가치를 지닌 18(10 + 4 + 4)를 사게되며 누적 가치는 36(18 + 18)이 된다. CPP고릴라의 상태는 3, 2가 된다.
6. JAVA고릴라에게 1개의 정보를 산다. 가장 큰 가치를 지닌 8을 사게되며 누적 가치는 44(36 + 8)이 된다. JAVA고릴라의 상태는 2가 된다.
7. PYTHON고릴라에 대해서는 아는 정보가 없으므로 거래할 수 없다.

예제를 이해한 것만으로 벌써 해쉬맵, 우선순위큐의 자료구조가 떠올랐다. 이제 문제를 풀어보자!

 

 

🔧 문제 풀이 과정을 정리해 보자.

1. 순서대로 정보를 입력받는다.
2. 1로 시작한다면 해쉬맵에 고릴라 정보를 저장해 준다.
3. 2로 시작한다면 해쉬맵에서 고릴라 정보를 찾아 정보를 구매한다.
4. 누적 결과를 반환한다.

 

🔹 순서대로 정보를 입력받는다.

- 정보는 시간 순서대로 주어지므로 정보를 입력 받으면서 로직을 실행한다.

 

🔹 쿼리가 1로 시작한다면 해쉬맵에 고릴라 정보를 저장해 준다. 이때 우선순위큐를 사용하여 가치를 정렬한다.

- 해쉬맵을 사용하는 이유는 같은 이름을 가진 고릴라의 정보가 중복해서 들어올 수 있기 때문이다.

- 해쉬맵으로 중복된 정보는 한 고릴라에게 연결해 주었다.

- 이미 해쉬맵에 해당 고릴라 정보가 있다면 연결된 우선순위큐(내림차순 정렬중인)에 입력된 정보를 추가해 준다.

- 해쉬맵에 고릴라 정보가 없다면 내림차순 정렬하는 우선순위큐를 만들어 해쉬맵에 저장해 준다. 

 

🔹 쿼리가 2로 시작한다면 해쉬맵에서 고릴라 정보를 찾아 정보를 구매한다.

- 예제의 마지막 정보를 보면 해쉬맵에 없는 PYTHON 고릴라와 거래를 하려고 하는데 이때 거래가 되면 안되므로 해쉬맵에 없는 key 정보는 continue하도록 했다.

- 고릴라의 정보를 구매할 때에는 count의 개수만큼 구매하되, map에 연결된 우선순위큐가 empty상태가 아닐 동안만 반복되도록 하였다.

 

🔹 누적 결과를 반환한다.

- 누적 결과의 최대값은 int범위를 벗어난다. 그러므로 long타입으로 선언한다.

 

코드

import java.io.*;
import java.util.*;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
 
        int q = Integer.parseInt(bf.readLine());
 
        Map<String, PriorityQueue<Integer>> map = new HashMap<>();
        long result = 0;
        for(int i = 0; i < q; i++) {
            String query = bf.readLine();
            StringTokenizer st = new StringTokenizer(query);
            
            int code = Integer.parseInt(st.nextToken());
            String name = st.nextToken();        
            int count = Integer.parseInt(st.nextToken());
            if(code == 1) {
                for(int j = 0; j < count; j++) {
                    if(!map.containsKey(name)) {
                        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
                        pq.add(Integer.parseInt(st.nextToken()));
                        map.put(name, pq);
                    } else {
                        map.get(name).add(Integer.parseInt(st.nextToken()));
                    }
                }
            } else {
                if(map.get(name) == null) continue;
                while(!map.get(name).isEmpty() && count > 0) {
                    result += map.get(name).poll();
                    count--;
                }
            }
        }
        System.out.println(result);
    }
}