[백준 BOJ / JAVA] 멀티버스 Ⅱ (18869번)

📘 1. 문제 소개

18869번: 멀티버스 Ⅱ

 

📘 2. 풀이

🧵 1. 좌표 압축

  문제의 포인트는 좌표 압축이다.

  좌표 압축이란 좌표 값들을 작은 범위의 값으로 압축하는 것이다. 수의 값에 상관없이 수의 대소관계만 알면 될 때 사용할 수 있다.

 

  -100, -4, 0, 3, 5000이라는 좌표가 있다고 해보자. 이를 배열처럼 표시한다면 다음과 같다.

-100	...	-4	...	0	...	3	...	5000
존재		존재		존재		존재		존재

  하지만 압축을 이용하여 대소관계만 파악한다면 다음과 같이 표현할 수 있다.

좌표 압축 값	0	1	2	3	4
실제 값	-1000	-4	0	3	5000

  좌표 압축을 이용하여 기존에 필요했던 -100 ~ 5000까지의 공간을 0 ~ 4까지의 공간으로 줄일 수 있다.

🧵 2. 풀이

  좌표 압축을 이해했다면 문제의 풀이법을 쉽게 생각할 수 있다. 두 우주가 균등하기 위해서는 결국 좌표 압축된 값이 일치하면 된다.

  2개의 우주에 속하는 행성의 크기가 각각 '1 3 2', '12 50 31이라고 해보자. 각 우주를 좌표 압축하면 아래와 같다.

• 1 3 2 → 1 3 2
• 12 50 31 → 1 3 2

  좌표 압축 값이 같으므로 결국 두 우주는 균등하다고 할 수 있다.

  좌표 압축 값과 균등 우주에 대한 이해가 어렵다면 인접한 값들을 부등호로 나타낸 경우를 생각해 보자. '< < = >'와 '< < = >'는 균등 우주고, '< > >'와 '> < <'는 균등 우주가 아니다.

🧵 3. 시간복잡도

  좌표 압축을 할 때 이분탐색을 이용해야 한다. 이분 탐색을 이용하지 않는다면 하나의 우주의 행성들을 좌표 압축하는데 N^2의 시간이 소요된다.

  반면 이분 탐색을 이용하게 되면 NlogN이 소요된다. 행성(N개)을 이분탐색(logN)을 이용하여 자신의 위치를 찾을 수 있기 때문이다.

 

📘 3. 코드

public class Main {

    static int  N, M;
    static int[][] nums, compressedNums;
    static String[] ss;
    static List<Integer>[] sortedNums;

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

        ss = in.readLine().split(" ");
        M = Integer.parseInt(ss[0]);
        N = Integer.parseInt(ss[1]);
        nums = new int[M][N];
        sortedNums = new ArrayList[M];

        for(int i = 0; i < M; i++) {
            Set<Integer> set = new HashSet<>();

            ss = in.readLine().split(" ");
            for(int j = 0; j < N; j++) {
                int num = Integer.parseInt(ss[j]);
                nums[i][j] = num;
                set.add(num);
            }

            // 이분탐색을 위한 정렬된 행성 저장
            sortedNums[i] = new ArrayList<>(set);
            Collections.sort(sortedNums[i]);
        }

        // 좌표 압축
        compressedNums = new int[M][N];
        for(int i = 0; i < M; i++) {
            for(int j = 0; j < N; j++) {
                // 이분 탐색 이용
                compressedNums[i][j] = Collections.binarySearch(sortedNums[i], nums[i][j]);
            }
        }

        // 우주의 좌표 압축 값들을 비교하여 우주가 균등한지 확인한다
        int cnt = 0;
        for(int i = 0; i < M; i++) {
            for(int j = i + 1; j < M; j++) {
                if(Arrays.equals(compressedNums[i], compressedNums[j]))
                    cnt++;
            }
        }

        System.out.println(cnt);
    }
}