[JAVA] 백준 18869번 【G5.멀티버스 Ⅱ】

문제

 

18869번: 멀티버스 Ⅱ

---

풀이

 

위 문제를 풀기 위해서는 좌표 압축을 사용해야한다.

 

좌표 압축에 대한 문제를 하나 풀어보면 좋다.

 

18870번: 좌표 압축

 

좌표 압축을 하면 아래와 같은 결과가 나온다.

 

 

즉, 특정 배열의 원소마다 그 원소보다 작은 원소가 몇개인지(중복을 제거하고)를 알 수 있는 결과가 나온다.

 

1000 보다 작은 원소는 999 한 개 이므로 1000에 해당하는 위치는 1 로 변경되고

 

999보다 작은 원소는 없으므로 999에 해당하는 위치는 0으로 변경된다.

 

💡 좌표 압축은 어렵게 생각할 필요가 없는게, 

배열의 중복을 제거하고 정렬시킨다음 이분탐색해서 인덱스를 구하면

그 값이 해당 원소보다 작은 원소의 개수임을 알 수 있다.

 

 

그러면 멀티버스 문제의 예제에 적용해보자.

 

 

 

각 우주를 좌표압축한 결과는 위와 같다.

 

좌표 압축을 한 결과가 같을 때, 균등한 우주임을 쉽게 파악할 수 있다.

 

따라서, 우리가 해야할 것은

 

각 우주를 좌표압축한 배열을 저장하고, 배열끼리 equals() 한지 비교하고 같다면 하나씩 카운트 해주면 된다!

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;


public class Main {
    int M;
    int N;
    int[][] spaces;
    public static void main(String[] args) throws IOException {
        new Main().sol();
    }

    private void sol() throws IOException {
        setUp();

        // 각 우주를 좌표 압축을 한다.
        for (int[] space : spaces) {
            compress(space);
        }

        System.out.println(getCnt());

    }

    private void setUp() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        M = Integer.parseInt(input[0]);
        N = Integer.parseInt(input[1]);
        spaces = new int[M][N];
        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                spaces[i][j] = Integer.parseInt(input[j]);
            }
        }
    }



    private void compress(int[] space) {
        int[] cloned = space.clone();
        // 이분 탐색을 위한 중복 제거와 정렬 작업
        int[] arr = Arrays.stream(cloned).sorted().distinct().toArray();

        for (int i = 0; i < N; i++) {
            // Java 에서 제공하는 이분탐색 메서드를 사용해도 된다.
//            space[i] = Arrays.binarySearch(arr, space[i]);
            space[i] = bs(arr, space[i]);
        }

    }

    private int bs(int[] arr, int target) {
        int left = 0, right = arr.length;
        while (left < right) {
            int mid = (left + right) / 2;
            if (target <= arr[mid]) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }


    private int getCnt() {
        int cnt = 0;
        for (int i = 0; i < M-1; i++) {
            for (int j = i+1; j < M; j++) {
                if (Arrays.equals(spaces[i], spaces[j])) {
                    cnt++;
                }
            }
        }
        return cnt;
    }


}