[백준] 18869. 멀티버스 Ⅱ

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

18869번: 멀티버스 Ⅱ

• 같은 우주임을 판별하려면 행성들을 정렬했을 때, 기존 인덱스 값을 기준으로 비교하면 된다.
  • ex, 행성1: 10, 30, 20 ➡️ 정렬 후 인덱스 값: 0, 2, 1
  • ex, 행성2: 30, 20, 10 ➡️ 정렬 후 인덱스 값: 2, 1, 0
  • ex, 행성3: 20, 50, 30 ➡️ 정렬 후 인덱스 값: 0, 2, 1
  • 결과: 행성1과 행성3은 균등함
• 따라서 기존 배열(ex, 10, 30, 20)과 정렬된 배열(ex, 10, 20, 30)이 있을 때, 정렬된 배열에 기존 배열의 값이 몇 번째 인덱스에 있는지 확인하면 된다. (ex, 0, 2, 1)
• 인덱스를 찾을 때 행성 개수 n개를 순차 탐색하면 O(n^2)의 시간 복잡도가 발생한다. 따라서 전체 코드의 시간 복잡도는 O(m * n^2)가 되어 시간 초과가 발생한다. 따라서 인덱스를 찾을 때 이분탐색을 통해 찾아야 한다O(nlogn). 
• 인덱스 값들로 이뤄진 배열 간에 비교할 때, 배열 간 비교는 Arrays.equals()를 사용하면 된다. 일차원 배열의 값들을 비교해주는 메소드이다.

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

// 시간 복잡도: O(m * nlogn)
public class Main {

    static int m; // 우주 개수
    static int n; // 행성 개수
    static int[][] arr;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());
        arr = new int[m][n];
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int[] oneArr = new int[n];

            for (int j = 0; j < n; j++) {
                oneArr[j] = Integer.parseInt(st.nextToken());
            }

            arr[i] = oneArr;
        }

        for (int i = 0; i < arr.length; i++) {
            int[] oneArr = arr[i];
            int[] sortedArr = oneArr.clone();
            Arrays.sort(sortedArr);
            // 이분탐색
            for (int j = 0; j < oneArr.length; j++) {
                oneArr[j] = calculateIdx(sortedArr, oneArr[j]);
            }
        }

        int answer = 0;
        for (int i = 0; i < m; i++) {
            for (int j = i + 1; j < m; j++) {
                if (Arrays.equals(arr[i], arr[j])) { // Arrays.equals: 두 배열의 값 비교
                    answer++;
                }
            }

        }
        System.out.println(answer);
    }

    // sortedArr 배열에서 target 숫자가 있는 인덱스를 찾아서 반환
    private static int calculateIdx(int[] sortedArr, int target) {
        int minIdx = 0;
        int maxIdx = sortedArr.length - 1;
        int midIdx = 0;
        while (minIdx <= maxIdx) {
            midIdx = (minIdx + maxIdx) / 2;
            if (sortedArr[midIdx] == target) {
                return midIdx;
            } else if (sortedArr[midIdx] < target) {
                minIdx = midIdx + 1;
            } else {
                maxIdx = midIdx - 1;
            }
        }
        return -1;
    }
}