[백준 알고리즘] 22252번: 정보 상인 호석 (JAVA)

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

22252번: 정보 상인 호석

소스코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		HashMap<String,PriorityQueue<Integer>> map = new HashMap<>();
		
		int n = Integer.parseInt(br.readLine());
		long ans = 0;
		
		for (int i=0; i<n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine()," ");
            
			int info = Integer.parseInt(st.nextToken()); // 쿼리 (1 or 2)
			String name = st.nextToken(); // 고릴라 이름
			int k = Integer.parseInt(st.nextToken()); // 정보 수
            
			if (info == 1) { // 쿼리가 1로 시작할 때
            	// 최대힙 만들기
				PriorityQueue<Integer> p = new PriorityQueue<>(Collections.reverseOrder()); 
				
				for (int j=0;j<k;j++) {
					p.add(Integer.parseInt(st.nextToken()));
				}
				
				if (map.containsKey(name)) { // map에 이미 등록되어 있으면, value에 입력값 추가
					for (int a=0;a<k;a++) {
						map.get(name).add(p.poll());
					}
				} else { // 없으면 새로 만들어준 힙큐를 map에 추가
					map.put(name,p);
				}
	
			} else { // 쿼리가 2일 때
				if (!map.containsKey(name)) { // 이름이 존재하지 않으면 continue
					continue;
				} else { // 있으면 k만큼 힙큐에서 제거하고 출력 값에 더해줌 
					while (!map.get(name).isEmpty() && k >0) {
						ans += map.get(name).poll();
						k --;
					}
				}

			}
	
		}
		System.out.println(ans);	
	}
}

 

풀이

★ 자바로 우선순위 큐를 사용하는 법을 연습하고, 더불어  HashMap에 데이터를 추가 및 삭제하는 방식을 익히기 위해 문제를 풀어봤습니다 !

 

★ 문제는 그렇게 복잡하지 않습니다. 고릴라가 가지고 있는 정보의 가치가 높은 순서대로 뽑아줘야 하기 때문에 정보 배열을 우선순위 큐로 만들어줍니다. 이때 가치가 높은 순서대로 뽑아야 하기 때문에 일반적인 최소힙이 아닌, 최대힙으로 힙큐를 구성해줘야 합니다. 그 후 쿼리가 1일 경우 고릴라와 그 정보를 HashMap에 key와 value로 넣어주고 2일 경우 해당 이름을 가지고 있는 고릴라를 찾아서 정보를 제거시켜줍니다.