백준 22252번 정보 상인 호석 G5 - Java, Hash, 우선순위 큐

 

아오 오래걸렸다

 

 

 

 

먼저 쿼리 개수가 주어진다.

이후로 1 또는 2의 쿼리 값이 주어지고, 고릴라의 이름. 정보의 개수 정보의 가치 가 주어진다.

문제를 한 20분 읽은거 같다. Cpp 5 10 4 2 8 2 라길래  5도 정보에 포함인줄 ....

 

이렇게 되겠다.

여기서 가장 큰 값만 가져오기 때문에 정렬이 필요한데 우선순위 큐를 활용했다.

우선순위 큐(Priority Queue)는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 것.

힙(Heap)으로 정렬하기에 시간 복잡도는 추출 삽입 모두 O(logn) 이다.

 

그리고 Map 을 편하게 쓰기위해 처음보는 메서드를 써봤는데

간단하게 key에 valuye가 존재하면 가져와서 사용하고, 없으면 새로 만들어주는 메서드다.

computeIfAbsent(K key, Function <? super K,? extends V> mappingFunction) 

 

key에 값이 존재한다면 NullPointerException.
key에 값이 존재하고, 람다식 함수의 결과가 Null이라면 해당 key를 삭제.
key에 값이 존재하고, 람다식의 결과가 Null이 아니라면, 이전 Value를 해당 key로 매핑하고 반환.

하는 특징이 있다.

 

< 같은 동작을 하지만 깔꼼!~~ >

Data data = map.computeIfAbsent(name, k -> new Data());

//            Data data = map.get(name);
//            if (data == null) {
//                data = new Data();
//                map.put(name, data);
//            }

 

import java.io.*;
import java.util.*;
 
 
public class Main { //Boj_22252_정보 상인 호석
 
    public static class Data {
        PriorityQueue<Integer> pq;
        Data(){
            // reverseOrder()로 큰 수가 우선순위가 높게해주었다.
            pq = new PriorityQueue<>(Collections.reverseOrder());
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        Map<String, Data> map = new HashMap<>();
        int n = Integer.parseInt(br.readLine());
        long sum = 0; // 이거 때문에 계속 틀렸었다. 최대 10^6 * 10^5이므로 long 사용 필요
 
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int query = Integer.parseInt(st.nextToken());
            String name = st.nextToken();
            int count = Integer.parseInt(st.nextToken());
 
            // 기존에 key에 value가 있는지 판단하기 위함.
            Data data = map.computeIfAbsent(name, k -> new Data());
 
            if (query == 1) { // 데이터 추가
                for (int j = 0; j < count; j++) {
                    int k = Integer.parseInt(st.nextToken());
                    data.pq.add(k);
                }
            } else if(query == 2) { // 데이터 구매
                for (int j = 0; j < count; j++) {
                    if (!data.pq.isEmpty()) {
                        sum += data.pq.poll();
                    }
                }
            }
        }
 
        System.out.println(sum);
        br.close();
    }
}