[JAVA]18869 멀티버스2 , 좌표압축

 📚 문제  

18869번: 멀티버스 Ⅱ

 

🔍 아이디어  

처음에는 그냥 기본적인 bruteforce풀이를 진행하였다. 골드 문제에 어울리지 않는다고 생각했는데 바로 시간초과가 났다.

이 풀이를 그대로 멀티버스 1번에 넣으니 통과되었다(브론즈 5)

 

못풀겠다 하고 침대에 누워있었는데 각 행성에 등수를 매기고 그 등수가 동일한 우주가 있다면 동일하게 균등하다고 할 수 있을 것 같다는 생각이 들었다. 그래서 싹 정렬을 하고 등수를 매겼다.

 

등수를 매길때 동일한 숫자는 동일한 등수를 주어야 하기 때문에 그냥 list에 넣고 indexOf를 이용해서 등수를 매겼다. 그런 후 해시에 해당 배열을 스트링 변환 후 마지막에 계산해서 답을 내었다 -> 시간 초과.

 

이후에 좌표 압축 기능을 확인하고 좌표압축방식으로 진행하였다. 좌표 압축은 아래 블로그에서 잘 설명 되어있어 참고하였다.

간단하게 설명하면 기존 값을 모두 리스트에 넣고 정렬한 후에 해시에 {정렬값, 현재 랭킹값}을 넣고 기존 배열을 다시 돌면서 해당 값에 해당하는 랭킹을 빼서 대체해주면 된다. 해당 방법이 아닌 이분 탐색을 이용하는 방법도 있는 것 같았다.

 

하지만 이렇게 해도 시간 초과가 나서 도대체 뭐지 하다가 등수 배열을 해시에 넣지않고 앞의 우주들 중 동일한 게 있다면 바로 정답 개수를 하나 증가하도록 하였다 이렇게 해서 통과하였다.(스트링이 길 것 같아서 불안하긴 했는데 여기서 시간초과라니이)

 

https://st-lab.tistory.com/279

[백준] 18870번 : 좌표 압축 - JAVA [자바]

 

📝 풀이 

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

public class Boj_18869_멀티버스2 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int galaxyCnt = Integer.parseInt(st.nextToken());//우주의 개수
        int planetCnt = Integer.parseInt(st.nextToken());//우주 행성의 수

        int[] map = new int[planetCnt];
        int[][] ranks = new int[galaxyCnt][planetCnt];

        List<Integer> sorted = new ArrayList<>();
        HashMap<Integer, Integer> sortedHash = new HashMap<>();
        int rank, cnt = 0;

        for (int i = 0; i < galaxyCnt; i++) {
            st = new StringTokenizer(br.readLine());
            sorted.clear();
            sortedHash.clear();

            for (int j = 0; j < planetCnt; j++) {
                map[j] = Integer.parseInt(st.nextToken());
                sorted.add(map[j]);
            }
            Collections.sort(sorted); //우주의 행성을 정렬한다.

            rank = 1;
            for (int j = 0; j < planetCnt; j++) {
                if (!sortedHash.containsKey(sorted.get(j)))
                    sortedHash.put(sorted.get(j), rank++); //각 숫자에 등수를 매긴다
            }

            for (int j = 0; j < planetCnt; j++) {
                ranks[i][j] = sortedHash.get(map[j]); //매겨진 등수를 각 행서의 위치에 등록해준다.
            }

            //자신보다 앞에 있는 우주들중에 평행한것이 있다면 추가한다.
            for (int p = 0; p < i; p++) {
                if (check(ranks[i], ranks[p])) {
                    cnt++;
                }
            }
        }
        
        System.out.println(cnt);
    }

    private static boolean check(int[] a, int[] b) {
        for (int i = 0; i < a.length; i++) {
            if (a[i] != b[i]) {
                return false; //만약 등수가 같지 않다면 바로 리턴한다. ( 균등하지 않다 )
            }
        }
        return true;
    }

}