BOJ 17140 이차원 배열과 연산

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

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

---

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

---

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

---

예제 입력 1

1 2 2
1 2 1
2 1 3
3 3 3

예제 출력 1

0

예제 입력 2

1 2 1
1 2 1
2 1 3
3 3 3

예제 출력 2

1

… 이하 예제 생략

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static class Check implements Comparable {
        int value, count;

        public Check(int value, int count) {
            this.value = value;
            this.count = count;
        }

        // 연산을 진행하며 수의 등장 횟수 기준 오름차순 정렬 (수의 등장 횟수가 동일할 경우, 수의 오름차순 정렬)하기 위한 compareTo 메소드
        @Override
        public int compareTo(Object o) {
            Check c = (Check) o;
            if (this.count == c.count)
                return this.value - c.value;
            return this.count - c.count;
        }
    }

    static int[][] arr = new int[3][3];

    static int r, c, k;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        r = Integer.parseInt(st.nextToken()) - 1;
        c = Integer.parseInt(st.nextToken()) - 1;
        k = Integer.parseInt(st.nextToken());

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

        // 최대 100번까지 연산을 반복하며, 목표 값을 찾는다.
        final int SEARCH_LEVEL = 100;
        for (int i = 0; i < SEARCH_LEVEL; i++) {
            if(r < arr.length && c < arr[0].length && arr[r][c] == k) {
                System.out.println(i);
                return;
            }

            calculate();
        }

        System.out.println(r < arr.length && c < arr[0].length && arr[r][c] == k ? SEARCH_LEVEL : -1);
    }

    static void calculate() {
        PriorityQueue<Check>[] queues; // 수의 등장횟수, 수의 크기 기준으로 새로운 배열의 각 행을 채우기 위한 우선순위 큐 배열

        // R 연산
        if(arr.length >= arr[0].length) {
            queues = new PriorityQueue[arr.length];
            int maxSize = Integer.MIN_VALUE; // 새로 생성할 배열의 최대 크기를 검사하기 위한 변수
            for (int i = 0; i < arr.length; i++) {
                queues[i] = new PriorityQueue<>();
                Arrays.sort(arr[i]); // 현재 배열에서 i번째 행을 오름차순으로 정렬시킴
                int j;
                // 처음에 나오는 0들을 건너뛰기 위한 반복문
                for (j = 0; j < arr[i].length && arr[i][j] == 0; j++) ;

                int v = arr[i][j], c = 0;
                // 큐에 50개가 offer 되었으면 그 이후 검사 생략
                for (; j < arr[i].length && queues[i].size() < 50; j++) {
                    if(v != arr[i][j]) {
                        queues[i].offer(new Check(v, c));
                        v = arr[i][j];
                        c = 1;
                    } else c++;
                }
                // 큐의 크기가 50이 넘지 않았다면, 마지막으로 검사한 수와 개수를 큐에 offer
                if(queues[i].size() < 50) queues[i].offer(new Check(v, c));
                // 검사 중인 행의 size가 이전 행 최대 크기보다 클 경우, maxSize 갱신
                maxSize = Integer.max(maxSize, queues[i].size());
            }

            // 큐에 담긴 검사 결과를 넣기 위해 maxSize에 맞는 새로운 배열 생성
            arr = new int[arr.length][maxSize * 2];
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr[0].length - 1; j += 2) {
                    // 차례로 큐에서 poll 하며 검사 결과를 배열에 넣음
                    Check check = queues[i].poll();
                    if(check != null) {
                        arr[i][j] = check.value;
                        arr[i][j + 1] = check.count;
                    }
                }
            }
            return;
        }

        // C 연산
        queues = new PriorityQueue[arr[0].length];
        int maxSize = Integer.MIN_VALUE;
        for (int i = 0; i < arr[0].length; i++) {
            queues[i] = new PriorityQueue<>();
            for (int j = 0; j < arr.length && queues[i].size() < 50; j++) {
                if(arr[j][i] == 0) continue;
                int v = arr[j][i], c = 1;
                for (int k = j + 1; k < arr.length; k++) {
                    if(arr[k][i] == v) {
                        c++;
                        arr[k][i] = 0; //중복 집계 방지
                    }
                }
                queues[i].offer(new Check(v, c));
                maxSize = Integer.max(maxSize, queues[i].size());
            }
        }

        arr = new int[maxSize * 2][arr[0].length];
        for (int i = 0; i < arr[0].length; i++) {
            for (int j = 0; j < arr.length - 1; j += 2) {
                Check check = queues[i].poll();
                if(check != null) {
                    arr[j][i] = check.value;
                    arr[j + 1][i] = check.count;
                }
            }
        }
    }
}