[BOJ 1202 보석도둑 java] 우선순위 큐 말고 다른 방법

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

1202번: 보석 도둑

 

이 문제의 풀이 계획

1. 보석을 가치는 높고 가치가 같다면 무게가 낮은 순으로 정렬을 한다.
2. 보석을 순회 하면서 넣을수 있는 가방 중에 가장 무게가 낮은 가방을 고르면 된다.

 

2번이 일반적인 풀이는 우선순위큐를 사용해서 쓸 수 있는 가방을 계속 넣었다 빼줬다 하면서 풀 수 있다.

 

여기서 나는 이진탐색 + union-find 의 find 알고리즘으로 풀이를 해보았다.

 

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

public class Main {
    static class Gem implements Comparable<Gem> {
        int m;
        int price;

        public Gem(int m, int price) {
            this.m = m;
            this.price = price;
        }

        @Override
        public int compareTo(Gem o) {
            return o.price == this.price ? this.m - o.m : o.price - this.price;
        }
    }

    static int N, K;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        PriorityQueue<Gem> priorityQueue = new PriorityQueue<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            priorityQueue.add(new Gem(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }

        int[] bags = new int[K];
        for (int i = 0; i < K; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }

        System.out.println(getMaxValue(priorityQueue, bags));
    }

    private static long getMaxValue(PriorityQueue<Gem> priorityQueue, int[] bags) {
        Arrays.sort(bags);
        int[] parents = new int[K + 1];
        for (int i = 1; i <= K; i++) {
            parents[i] = i;
        }

        long values = 0;
        while (!priorityQueue.isEmpty()) {
            Gem cur = priorityQueue.poll();

            if (findBag(parents, bags, cur.m)) {
                values += cur.price;
            }
        }

        return values;
    }

    private static boolean findBag(int[] parents, int[] bags, int m) {
        int idx = binarySearch(bags, m);

        if (idx < K) {
            int parent = find(parents, idx);
            if (parent < K) {
                parents[parent] = parent + 1;
                return true;
            }
        }

        return false;
    }

    private static int find(int[] parents, int node) {
        if (parents[node] == node) {
            return node;
        }

        return parents[node] = find(parents, parents[node]);
    }

    private static int binarySearch(int[] bags, int m) {
        int left = 0;
        int right = bags.length - 1;

        while (left <= right) {
            int mid = (left + right) >> 1;

            if (bags[mid] < m) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return left;
    }

}

 

아 물론 처음에 정렬은 우선순위큐를 사용하였지만 여기서는 그냥 정렬로 써도 무방하다. (근데 속도는 우선순위 큐가 가장 빠르더라..)

 

함수 소개

func : getMaxValue()  => 가장 가치가 높으면서 무게가 낮은 보석을 순차적으로 순회하면서

func : binarySearch() => 넣을 수 있는 가방이 있는지 이진탐색으로 탐색한다.

있는 경우,

이 때 이미 사용한 가방은 사용할 수가 없는데, 배열에서 중간 원소를 없애기는 비용이 너무 크므로 방문 체크만 해주고 그 다음 사용 가능한 원소를 저장해두는 방식을 떠올렸다.

 

func : find() => union-find 알고리즘에서 find 알고리즘을 따온 것이고 사용한 가방의 다음 번호를 저장한다. 그럼 연쇄적으로는 다음 가방도 사용한 가방이면 끝까지 가서 사용 안 된 다음 가방을 찾을 것이다.

 

경로 최적화 부분으로 이 알고리즘은 상수의 시간 복잡도를 갖는다고 한다.

parents[node] = find(parents, parents[node]);

https://ko.wikipedia.org/wiki/%EC%84%9C%EB%A1%9C%EC%86%8C_%EC%A7%91%ED%95%A9_%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0#%EA%B2%BD%EB%A1%9C_%EC%95%95%EC%B6%95

 

 

 

후기:

우선순위큐를 사용하는 풀이보다 이게 더 시간 빠르게 나온 것 같아서 이런 풀이도 있다~ 입니다.