백준 18868 자바 - 멀티버스 Ⅰ(boj 18868 java)

문제 : boj18868

 

 

  주어진 대로 구현하면 되긴 한다. 내 경우엔 입력받은 값을 전처리해서 좀 더 쉽게 만들었다. 각 우주에 있는 모든 행성의 모든 쌍에 대해 순서대로 규칙을 만들어 하나의 String으로 만들었다. 예를들어 어떤 우주에 4개의 행성이 있었다면 1-2, 1-3, 1-4, 2-3, 2-4, 3- 4 순서대로 모든 쌍을 비교한다. 그래서 "+-+=++"와 같은 형태의 해당 우주의 모든 행성의 크기 규칙에 대한 String을 만드는 것이다.

 

  그럼 최종적으로 M개의 String에 대해 모든 쌍을 확인 했을 때 동일한 String을 가진 행성이 몇 쌍 존재하는지만 확인하면 되는 문제로 변경된다. 즉 모든 쌍에 대한 단순 비교 로직 2개만 있으면 풀 수 있으므로 구현의 복잡도가 많이 줄어든다.

 

  에를들어 다음의 입력을 봐보자.

3 4
1 3 2 1
12 50 31 12
5 6 7 5

  위의 입력값을 위에 설명한 풀이 로직대로 진행하면 다음과 같다.

 

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        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());
        String[] arr = new String[m];
        for (int i = 0; i < m; i++) {
            StringBuilder sb = new StringBuilder();
            st = new StringTokenizer(br.readLine());
            int[] tmp = new int[n];
            for (int j = 0; j < n; j++)
                tmp[j] = Integer.parseInt(st.nextToken());
            for (int j = 0; j < n-1; j++) {
                for (int k = j+1; k < n; k++) {
                    if (tmp[k]>tmp[j]) sb.append('+');
                    else if (tmp[k]<tmp[j]) sb.append('-');
                    else sb.append('=');
                }
            }
            arr[i] = sb.toString();
        }

        int cnt = 0;
        for (int i = 0; i < m-1; i++) {
            for (int j = i+1; j < m; j++) {
                if (arr[i].equals(arr[j])) cnt++;
            }
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}