[BOJ] 17140번: 이차원 배열과 연산

ㅇㅅㅇ..하..넘무 어려웠다ㅜ 

---

문제

크기가 3×3인 배열 A가 있다. 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을 넘어가는 경우에는 -1을 출력한다.

---

🔍 내 풀이

문제 그대로 만들면 되는데 이차원 배열 고민하다가 머리에 쥐나는 문제였다...

 

수행 flow를 살펴보면,

행렬 입력 -> 반복 ( 연산에 의한 업데이트 -> 수행 완료 조건 체크 ) -> 조건을 만족하기 까지 걸린 시간 출력 ( 100초과 시 -1 )

 

이 과정이다 이 틀 그대로 나는 연산함수가 반복되며 연산 수행 전 완료 조건을 체크하도록 했다.

한가지 유의할 것이 R, C연산에 의해 수행될 정렬을 Sort함수 구현과 행렬 업데이트 였다.

 

정렬을 위해서는 Counter라는 객체를 생성해 활용했다.

숫자 정보 = k, 몇 번 존재했는지 count= v로 정보를 담게 되며 comparable을 활용해 정렬기준을 잡아주었다.

객체를 정렬하고 순서대로 리스트에 객체의 정보를 옮겨 담으면 된다. [k, v, k, v, ...] 이런 형태로

그리고 정렬된 정보를 새로 초기화된 행렬에 업데이트 해주면 된다. -> 이 부분은 코드를 참고하자! 

 

정렬 이후 행렬 업데이트시 행렬의 크기가 최초 입력 크기로 고정되어 있다면 반복적으로 크기가 변동되는 상황을 대처하기 어렵다.

그러므로 최대 크기보다 조금 큰 이차원 배열을 생성해 활용했다. 문제에 행렬의 최대 크기가 100을 넘지않는다는 조건이 있다.

그리고 매번 (행, 열)크기를 업데이트 해주어 R, C연산시 참조 범위 선정에 활용했다.

 

연산, 행렬 update가 모두 완료된 행렬로 다시 연산을 수행하는 재귀 함수를 작성했다.

 

✔️ 내 코드

package BOJ;

import java.util.*;

public class DoubleArray {
    static int time = 0;
    static int r, c, k;
    static int[][] A = new int[102][102];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        r = sc.nextInt();
        c = sc.nextInt();
        k = sc.nextInt();
        for(int i=1; i<=3; i++){
            for(int j=1; j<=3; j++){
                A[i][j] = sc.nextInt();
            }
        }

        calc(A, 3, 3);
        System.out.println(time);
    }
    static void calc(int[][] A, int row, int col){
        if(time>100 || A[r][c] == k){
            if(time>100){
                time = -1;
            }
        } else {
            time++;
            int[][] tmp = new int[102][102];
            int newSize = 0;
            if(row>=col){
                // R 연산 수행
                for(int i=1; i<=row;i++){
                    int[] sortedRow = sort(A[i],col);
                    for(int j=1; j<=sortedRow.length; j++){
                        tmp[i][j] = sortedRow[j-1];
                    }
                    if(newSize<=sortedRow.length){
                        newSize = sortedRow.length;
                    }
                }
                if (newSize > 100){
                    newSize = 100;
                }
                calc(tmp, row, newSize);
            } else {
                // C 연산
                for(int i=1; i<=col; i++){
                    int[] colList = new int[row+1];
                    for(int j=1; j<=row; j++){
                        colList[j] = A[j][i];
                    }
                    int[] sortedCol = sort(colList,row);
                    for(int k=1; k<=sortedCol.length; k++){
                        tmp[k][i] = sortedCol[k-1];
                    }
                    if(newSize <=sortedCol.length){
                        newSize = sortedCol.length;
                    }
                }
                if (newSize > 100){
                    newSize = 100;
                }
                calc(tmp, newSize, col);
            }
        }
    }
    static int[] sort(int[] rowValue, int len){
        int[] cnt = new int[101];
        for(int i=1; i<=len; i++){
            if(rowValue[i]!=0) {
                cnt[rowValue[i]]++;
            }
        }
        // value기준 오름차순 정렬, key 기준 내림차순 정렬
        ArrayList<Counter> cntList = new ArrayList<>();
        for(int i=0; i<cnt.length; i++){
            if(cnt[i]!=0){
                cntList.add(new Counter(i, cnt[i]));
            }
        }
        Collections.sort(cntList);
        int[] sorted = new int[cntList.size()*2];
        int j=0;
        for(int i=0; i<cntList.size(); i++){
            sorted[j] = cntList.get(i).k;
            sorted[j+1] = cntList.get(i).v;
            j+=2;
        }
        return sorted;
    }
}
class Counter implements Comparable<Counter>{
    int k;
    int v;

    public Counter(int k, int v){
        this.k = k;
        this.v = v;
    }

    @Override
    public int compareTo(Counter counter) {
        if(this.v == counter.v){
            return this.k >= counter.k ? 1 : -1;
        }
        return this.v >= counter.v ? 1 : -1;
    }
}

---

• 문제 출처: https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산