멀티버스 Ⅱ

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

 

알고리즘 분류

• 정렬
• 값 / 좌표 압축

 

접근 방법

처음에, 어떻게 각 우주들의 대소관계를 비교할지 애를 먹었다. 내가 처음에 떠올린 방법은

Ai < Aj → Bi < Bj 일 때 배열에 1 저장
Ai = Aj → Bi = Bj 일 때 배열에 0 저장
Ai > Aj → Bi > Bj 일 때 배열에 -1 저장

 

이런식으로 각 우주의 대소관계를 저장해주려고 했는데 모든 배열을 순회하는데만 O(N^2) * 100이라 시간초과가 발생한다.

 

문제에서 우주의 개수가 100개이고, 각 우주의 크기가 10,000이기 때문에 시간복잡도를 줄여야 한다. 고민해봐도 답을 떠올리지 못해 GPT한테 물어봤는데 정말 괜찮은 풀이를 알려줬다.

 

[1, 3, 2] 라는 원래 배열이 있다고 가정하자.

해쉬맵을 선언하여 [행성, 순서] 형태로 선언을 하자. 그 뒤에, [1, 3, 2]의 배열을 copy해서 오름차순으로 정렬되게끔 한다. 그렇게 되면 [1, 2, 3] 배열이 나올 것이고, map에 차례로 넣어준다.

그러고 다시 int 배열을 통해 map의 value값들을 저장하면, 최종적으로 대소 관계에 비례하는 [0, 2, 1]과 같은 형태의 배열을 얻을 수 있다. 이런식으로 모든 배열들을 `좌표 압축`을 진행해주고 List<int []>에 넣어줘서 리스트를 순회하며 동일한 배열인지 비교해주면 된다.

Arrays.equals()

배열 비교를 할 때 arr[1].equals(arr[2]) 이런식으로 비교를 했더니 값이 출력되지 않아서 봤더니 equals() 메서드는 주소 값을 비교하기 때문에 false가 나올 수 밖에 없다. arr[1]과 arr[2]는 서로 다른 배열이기 때문이다.

따라서, Arrays.equals()를 통해서 배열의 일치 여부를 판단해 주었다.

 

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.StringTokenizer;

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

        List<int[] > list = new ArrayList<>();

        for(int i = 0; i < m; i++) {
            int[] arr = new int[n];
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                arr[j] = Integer.parseInt(st.nextToken());
            }

            int[] sorted = calc(arr);
            list.add(sorted);
        }

        int cnt = 0;
        for(int i = 0; i < list.size(); i++) {
            for(int j = i + 1; j < list.size(); j++) {
                int[] arr1 = list.get(i);
                int[] arr2 = list.get(j);
                if (Arrays.equals(arr1, arr2)) {
                    cnt++;
                }
            }
        }
        System.out.println(cnt);
    }

    public static int[] calc(int[] arr) {
        int [] sorted = arr.clone();
        Arrays.sort(sorted);

        Map<Integer, Integer> map = new HashMap<>();

        int idx = 0;
        for(int value : sorted) {
            map.put(value, idx++);
        }

        int [] res = new int[arr.length];
        for(int i = 0; i < res.length; i++) {
            res[i] = map.get(arr[i]);
        }
        return res;
    }
}