[백준] 22252 정보 상인 호석 -Java

 

 

 

정보를 ArrayList에 저장하고 sort를 통해 정렬한 후 결과값을 찾을 수도 있겠지만, Q의 범위가 100,000이니 sort를 진행할 시 시간 초과가 나올 것이다.

 

기본으로 sort가 되어 있는 heap자료구조를 통해 구현된 PriorityQueue를 사용해서 문제를 해결하자.

 

1을 입력받았을 때 고릴라의 이름과 이름에 따른 우선순위 큐를 만들어야 한다. HashMap을 사용해서 두 가지 정보를 한 번에 저장하자.

 

2를 입력받았을 때 입력받은 고릴라에게서 정보를 구매해야 한다. 1에서 만든 HashMap이 있을 경우에 정보를 가져오자.

 

 

 

Java

 

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

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

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

      HashMap<String, PriorityQueue<Integer>> hm = new HashMap<>();

      long sum =0;

      for(int i=0; i<N; i++){
        st = new StringTokenizer(br.readLine(), " ");
        int command = Integer.parseInt(st.nextToken());
        String name = st.nextToken();
        if(command==1){
          if(hm.get(name) == null){
            hm.put(name, new PriorityQueue<>(Collections.reverseOrder()));
          }

          PriorityQueue<Integer> pq = hm.get(name);

          int k = Integer.parseInt(st.nextToken());
          for(int j=0; j<k; j++){
            pq.offer(Integer.parseInt(st.nextToken()));
          }
      
          
        }else if(command==2){
          if(hm.get(name) == null){
            hm.put(name, new PriorityQueue<>(Collections.reverseOrder()));
          }
          PriorityQueue<Integer> pq = hm.get(name);

          int temp = 0;
          int num = Integer.parseInt(st.nextToken());
          if(pq.size() > num){
            temp = num;
          }else{
            temp = pq.size();
          }

          for(int j=0; j<temp; j++){
            sum = sum + pq.poll();
          }
        }
      }
      
      System.out.println(sum);

       
    }
}