[Baekjoon] 18869 멀티버스 Ⅱ (Java)

문제 링크

백준-18869 멀티버스 Ⅱ

문제

M개의 배열이 주어진다. 각 배열을 하나의 우주로 칭한다.
각 배열의 모든 임의의 i,j번째 요소에 대해서 대소관계가 일치한다면 균등한 우주의 쌍이다.

• Ai < Bj -> Bi < Bj
• Ai = Aj -> Bi = Bj
• Ai > Aj -> Bi > Bj
  균등한 우주의 쌍 개수를 구하는 문제이다.

풀이

처음 문제 조건을 잘못 이해해서 바로 옆 숫자와의 대소관계만 확인하면 된다고 생각했지만 아니었다.
모든 임의의 i,j번째에 대해서 대소관계가 성립해야한다. 이 대소관계를 파악하기 위해 좌표압축 알고리즘이 사용된다.

좌표압축이란, 넓게 퍼저있는 수들을 압축해서 각 수들의 대소관계를 정규화 시키는 알고리즘이다. 즉 해당 배열에서 몇번째로 큰 수인지로 다시 표현한다.

방법은 다음과 같다.
1. 기존 배열에 존재하는 요소들을 새로운 배열에 넣고 정렬한다.
-> 이 때 중복되는 요소가 존재할 경우 결과가 부정확해질 가능성이 있으므로 중복을 제거한 후 정렬했다.
2. 기존 배열을 확인하며 정렬된 새로운 배열의 몇번째에 존재하는 수인지 확인 후 값을 대체한다.
-> 이 과정에서 이분탐색을 활용하여 시간복잡도를 최적화한다.

이렇게 좌표압축 시킨 모든 우주들을 서로 비교해보며, 같은 우주의 개수를 센다.

코드

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

public class Main{

    private static int N, M;
    private static int answer;
    private static List<List<Integer>> Spaces = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br  = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        M = Integer.parseInt(st.nextToken());
        N = Integer.parseInt(st.nextToken());

        for(int i=0; i<M; i++){
            st = new StringTokenizer(br.readLine(), " ");
            List<Integer> space = new ArrayList<>();
            Set<Integer> set = new HashSet<>();
            for(int j=0; j<N; j++){
                int planet = Integer.parseInt(st.nextToken());
                set.add(planet);
                space.add(planet);
            }

            List<Integer> clone = new ArrayList<>(set);
            Collections.sort(clone);

            for(int j=0; j<N; j++){
                int idx = Collections.binarySearch(clone, space.get(j));

                space.set(j, idx);
            }
            Spaces.add(space);
        }

        for(int i=0; i<M; i++){
            for(int j=i+1; j<M; j++){
                if(Arrays.equals(Spaces.get(i).toArray(), Spaces.get(j).toArray())) answer++;
            }
        }

        System.out.println(answer);


        br.close();
        bw.flush();
        bw.close();
    }

}