문제 이해

어떤 이름을 가진 고릴라는 $C_1, C_2, ..., C_k$만큼의 가치 있는 정보 K를 가지고 있다.

호석이는 특정 고릴라로부터 b개의 정보를 구매할 수 있는데, 호석이가 정보를 구매하자마자 고릴라는 해당 정보를 파기한다.
만약 고릴라가 가지고 있는 정보보다 많은 정보를 원하면 고릴라가 가진 모든 정보를 구매하는 것으로 끝낸다.

호석이가 정보들을 구매하는 데 쓴 돈의 총합을 구하는 문제이다.

---

문제 풀이

우선순위 큐를 활용하면 바로 해결되는 문제인 것 같다.

HashMap을 활용하여 Key는 고릴라 이름, Value에는 정보의 가치를 기준으로 하는 우선순위큐(내림차순)를 넣어주어 풀면 된다

---

코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();
		HashMap<String, PriorityQueue<Integer>> name = new HashMap<>();
        
		int N = sc.nextInt();
		
		long ans = 0;
		
		for(int rec=0;rec<N;rec++) {
			int cs = sc.nextInt();
			String name_tmp = sc.next();
			int count = sc.nextInt();
			
			
			if(cs==1) {
				if(name.get(name_tmp)==null) {
                // 처음 Search된 고릴라인 경우 HashMap에 추가
                // Collections.reverseOrder()로써 내림차순 우선순위 큐로 만듦
					name.put(name_tmp, 
                       new PriorityQueue<>(Collections.reverseOrder()));
				}
				
				for(int i =0;i<count;i++) {
                // cs = 1일 경우 데이터를 추가해야 함
					int tmp = sc.nextInt();
					name.get(name_tmp).add(tmp);
				}
			}
			else {
            // cs = 2. 즉 데이털 사는 상황
				if(name.get(name_tmp)!=null) {
					// 해당 이름을 가진 정보상 고릴라가 없을 수도 있다.
					int number = Math.min(count,
                                             name.get(name_tmp).size());
                    // 원하는 숫자만큼 사던가, 가지고 있는 모든 정보를 사던가
                    // 두 개 중 작은 것만큼의 정보를 살 수 있다.
					for(int i =0;i<number;i++) {
						ans+=name.get(name_tmp).poll();
					}
				}
			}
		}
		
		System.out.println(ans);
	}
	
	static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() // 빠른 입력을 위한 클래스
}

---

결과

• 시간 초과, 틀렸습니다 : 처음에는 PriorityQueue를 배열 형식으로 하고 싶어서 HashMap으로 이름과 index를 연결하고 해당 index의 PriorityQueue를 연결하는 방식을 활용했는데, 이러다보니 시간 초과 및 구현 실수로 틀렸습니다가 발생하였다.

• 런타임 에러 : 고릴라가 정보를 요청한 것보다 적게 가지고 있으면 가진 모든 데이터를 반환하고 종료해야 하는데 이 부분을 구현하지 않았다.