[백준 18869] 멀티버스 Ⅱ - JAVA

BOJ Link

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

 

 

 

풀이 과정

1. 아래 조건을 만족해야 한다.

• Ai < Aj → Bi < Bj
• Ai = Aj → Bi = Bj
• Ai > Aj → Bi > Bj

=> 우선, 배열 A와 B를 value에 따라 정렬 했을 때, idx 순서가 같으면 된다.

 

2. 위 로직만 적용했을 때의 반례

A = [1, 1, 1]

B = [1, 1, 2]

 

 

오름차순 정렬을 했을 때, 둘 다 idx는 [0, 1, 2] 이다.

그러나, A1 = 1, A2 = 1, B1 = 1, B2 = 2 이기 때문에

 

• A1 = A2
• B1 < B2

꼴이 되어 조건을 만족하지 않는다.

=> 따라서, rank를 부여하고 idx와 같이 비교한다.

 

3. 복기

문제를 풀고나서 알았는데, 이는 좌표압축 기법을 사용하는 문제였다.

차이점은, 비교하는 행성간에는 size가 같아야 하므로 중복제거를 하면 안된다.

 

또한, 초기 정답 코드에는

 

Dense Ranking :

중복 값이 있으면 동일한 순위를 부여하고, 그다음 값은 해당 순위 수를 건너뛰어 순위를 부여하는 방식

 

을 적용했는데 그럴 필요까진 없었다.

단순히 중복 값이 있으면 동일한 순위를 부여하면 끝이었다. 이는 주석처리 했다.

 

제출 코드

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

class Pair implements Comparable<Pair> {
    int idx, val;

    Pair(int idx, int val) {
        this.idx = idx;
        this.val = val;
    }

    @Override
    public int compareTo(Pair o) {

        if (this.val == o.val)
            return this.idx - o.idx;

        return this.val - o.val;
    }
}

class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        String s;
        int ans = 0;

        //3 ≤ N ≤ 10,000
        List<Pair[]>[] total = new List[10001];
        
        for (int i = 0; i < 10001; i++) {
            total[i] = new ArrayList<>();
        }

        while ((s = br.readLine()) != null) {
            
            // val 기준 오름차순 정렬, val이 같다면 idx 기준 오름차순 정렬 list
            List<Pair> list = new ArrayList<>();
            
            st = new StringTokenizer(s);
            int idx = 0;
            while (st.hasMoreTokens()) {
                list.add(new Pair(idx++, Integer.parseInt(st.nextToken())));
            }

            int L = list.size();
            Collections.sort(list);

            // idx별로 rank를 부여할 배열
            Pair[] ranked = new Pair[L];

            int rank = 0;
//            int weight = 1;

            // 1 ≤ 행성의 크기 ≤ 1,000,000
            int prev = -1;

            for (int i = 0; i < L; i++) {
                Pair pair = list.get(i);
                int val = pair.val;

                if (val == prev) {
                    ranked[i] = new Pair(pair.idx, rank);
//                    weight++;
                } else {
                    rank++;
//                    rank = rank + weight;
                    ranked[i] = new Pair(pair.idx, rank);
//                    weight = 1;
                }

                prev = val;
            }

            total[L].add(ranked);
        }

        for (int i = 0; i < 10001; i++) {
            List<Pair[]> cur = total[i];
            int C = cur.size();
            if (C < 2) continue;

            for (int l = 0; l < C - 1; l++) {
                Pair[] la = cur.get(l);

                for (int r = l + 1; r < C; r++) {
                    Pair[] ra = cur.get(r);
                    boolean same = true;

                    for (int at = 0; at < la.length; at++) {
                        if (la[at].idx != ra[at].idx || la[at].val != ra[at].val) {
                            same = false;
                            break;
                        }
                    }

                    if (same)
                        ans++;
                }
            }
        }

        System.out.println(ans);
    }
}