백준 1202 보석 도둑 Java [그리디, 우선순위큐]

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

1202번: 보석 도둑

 

보석과 가방이 300000개로 NlogN 시간복잡도 안에 처리해야한다

결과값은 최대가치 X N의 최대값 = 100만 x 30만 으로 long타입으로 선언해야한다

가방에 넣을 보석을 찾기 위해 우선순위큐에 가치 기준으로 넣어 줬다

 

가방의 갯수 체크를 위한 HashMap과

가방 무게 정렬 및 조회, 삭제를 위한 TreeSet 2개의 자료구조를 사용했다

HashMap에 가방 체크 후 있으면 숫자 1더하고

없으면 TreeSet 에 가방 무게 넣고 HashMap에 키 값 생성을 해줬다
조회는 TreeSet의 메서드인 같거나 높은 것을 조회하는 ceiling을 사용했다

( * 같거나 낮은 것을 조회할 때는 floor를 사용하면 된다 )

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        PriorityQueue<int[]> gems = new PriorityQueue<>(Comparator.comparingInt((int[] o) -> o[1]).reversed());
        HashMap<Integer, Integer> bags = new HashMap<>();
        TreeSet<Integer> bagSet = new TreeSet<>();
        long result = 0;
        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            gems.add(new int[]{m, v});
        }
        for (int k = 0; k < K; k++) {
            int bag = Integer.parseInt(br.readLine());
            if (!bags.containsKey(bag)) bagSet.add(bag);
            bags.put(bag, bags.getOrDefault(bag, 0) + 1);
        }

        while (!gems.isEmpty()) {
            int[] gem = gems.poll();
            if (!bagSet.isEmpty()) {
                if (bagSet.ceiling(gem[0]) != null) {
                    int bag = bagSet.ceiling(gem[0]);
                    if (bags.get(bag) == 1) bagSet.remove(bag);
                    bags.put(bag, bags.get(bag) - 1);
                    result += gem[1];
                }
            }
        }
        System.out.println(result);
    }
}

 

처음에 가방 갯수를 체크하는 HashMap 대신 배열에 담아줬는데 1억개 만드니까 메모리 초과가 떴다

문제 조건이 256mb인데 int배열 1억개는 약 382mb이다

어차피 가방 1개당 물건 1개 넣고 최대 무게가 100만이니까

배열을 100만까지만 만들고 가방무게를 100만 넘어가면 100만으로 처리해도 됐을 것 같다

 

마지막으로 자바 컬렉션 메서드들의 시간복잡도에 대해 찾아보았다

https://gist.github.com/psayre23/c30a821239f4818b0709

Runtime Complexity of Java Collections