[백준 골드4] 17140번: 이차원 배열과 연산 (구현, 정렬) - Java

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
예제 입력 3 
1 2 3
1 2 1
2 1 3
3 3 3
예제 출력 3 
2
예제 입력 4 
1 2 4
1 2 1
2 1 3
3 3 3
예제 출력 4 
52
예제 입력 5 
1 2 5
1 2 1
2 1 3
3 3 3
예제 출력 5 
-1
예제 입력 6 
3 3 3
1 1 1
1 1 1
1 1 1
예제 출력 6 
2

---

알고리즘: 구현, 정렬, 시뮬레이션, 집합과 맵

풀이

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다고 했으므로 int 2차원 배열을 100x100 크기로 만들고 rowLength, colLength로 경계를 표시해 크기를 조절했다.

r연산은 arr[i]를 바로 사용할 수 있었지만 c연산은 그럴 수 없어 따로 int[] 배열에 복사해 정렬했다.

 

행 길이 계산에 rowLength, newRowLength, localRowLength를 변수를, 열 길이 계산에 마찬가지로 colLength, newColLength, localColLength를 사용해 길이 갱신을 진행했다.

r연산에서 정렬 시 범위를 0, colLength로 제한하고 값이 0인 경우 continue시켜줘야 하는  부분에서 조금 헤맸다. (0 부분이 정렬에 포함되면 안 되기 때문에)

둘 다 List<int[]> freqList에 (값, 빈도)를 삽입하는데 정렬기준을 커스텀하기 위해 람다식으로 Comparator를 생성해 정렬시켰다. (1번째 인덱스부터 비교, 같은 경우 0번째 인덱스를 비교)

                    freqList.sort((a, b) -> {
                        if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
                        return Integer.compare(a[0], b[0]);
                    });

 

Integer.compare()의 생김새:
- 시그니처: public static int compare(int x, int y)

- 두 개의 int 값 x와 y를 받아 비교하여 x가 y보다 작으면 음수, 같으면 0, 크면 양수를 반환합니다. 

이에 따라 매개변수를 (a, b) 순서로 전달하면 오름차순, (b, a) 순서로 전달하면 내림차순으로 전달된다.

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

public class Main
{
    static int[][] arr = new int[100][100];
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int r = Integer.parseInt(s[0])-1;
        int c = Integer.parseInt(s[1])-1;
        int k = Integer.parseInt(s[2]);
        for(int i=0; i<3; i++) {
            s = br.readLine().split(" ");
            for(int j=0; j<3; j++) {
                arr[i][j] = Integer.parseInt(s[j]);
            }
        }
        int rowLength = 3;
        int colLength = 3;
        int count=0;
        while(count <= 100) {
            if(arr[r][c]==k){
                System.out.println(count);
                return;
            }
            // r연산
            if (rowLength >= colLength) {
                int newColLength = 0;
                for (int i=0; i<rowLength; i++) {
                    Arrays.sort(arr[i], 0, colLength);
                    List<int[]> freqList = new ArrayList<>();
                    int cnt=1;
                    for(int j=0; j<colLength; j++) {
                        if(arr[i][j] == 0) continue;
                        if (j != colLength-1 && arr[i][j] == arr[i][j+1]) {
                            cnt++;
                        } else {
                            freqList.add(new int[]{arr[i][j], cnt});
                            cnt = 1;
                        }
                    }
                    freqList.sort((a, b) -> {
                        if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
                        return Integer.compare(a[0], b[0]);
                    });
                    int j=0;
                    int localColLength = 0;
                    for (int[] pair : freqList) {
                        if (j>=100) break;
                        arr[i][j++] = pair[0];
                        if (j>=100) break;
                        arr[i][j++] = pair[1];
                        localColLength+=2;
                    }
                    if (newColLength < localColLength)
                        newColLength = localColLength;
                    for(; j<100; j++) {
                        arr[i][j] = 0;
                    }
                }
                colLength = newColLength;
            }
            // c연산
            else {
                int newRowLength = 0;
                int[] colArr = new int[rowLength];
                for (int j=0; j<colLength; j++) {
                    for(int i=0; i<rowLength; i++) {
                        colArr[i] = arr[i][j];
                    }
                    Arrays.sort(colArr);
                    
                    List<int[]> freqList = new ArrayList<>();
                    int cnt=1;
                    for(int i=0; i<rowLength; i++) {
                        if(colArr[i] == 0) continue;
                        if (i != rowLength-1 && colArr[i] == colArr[i+1]) {
                            cnt++;
                        } else {
                            freqList.add(new int[]{colArr[i], cnt});
                            cnt = 1;
                        }
                    }
                    freqList.sort((a, b) -> {
                        if (a[1] != b[1]) return Integer.compare(a[1], b[1]);
                        return Integer.compare(a[0], b[0]);
                    });
                    int i=0;
                    int localRowLength = 0;
                    for (int[] pair : freqList) {
                        if (i>=100) break;
                        arr[i++][j] = pair[0];
                        if (i>=100) break;
                        arr[i++][j] = pair[1];
                        localRowLength+=2;
                    }
                    if (newRowLength < localRowLength)
                        newRowLength = localRowLength;
                    for(; i<100; i++) {
                        arr[i][j] = 0;
                    }
                }
                rowLength = newRowLength;
            }
            count++;
        }
        System.out.println(-1);
    }
}