백준 17140번 : 이차원 배열과 연산 (c++)

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

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을 출력한다.

예제 입력 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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[100][100];
int R,C,K;

int solve(){

    int rsize = 3, csize=3;

    for(int t=0;t<=100;t++){
        if(arr[R][C]==K){
            return t;
        }

        if(rsize>=csize){
            for(int i=0;i<rsize;i++){
                vector <pair<int, int>> nums;
                nums.clear();
                int cnt[101]={0,};
                for(int j=0;j<csize;j++){
                    cnt[arr[i][j]]++;
                }
                for(int c=1;c<=100;c++){
                    if(cnt[c]>0){
                        nums.push_back({cnt[c],c});
                    }
                }
                sort(nums.begin(), nums.end());
                int idx = 0;
                for(auto pair : nums){
                    if (idx >=99) break;
                    arr[i][idx++] = pair.second;
                    arr[i][idx++] = pair.first;
                }
                csize = max(csize,idx);
                for(;idx<100;idx++){
                    arr[i][idx] = 0;
                }
            }
        }else{
            for(int j=0;j<csize;j++){
                vector <pair<int, int>> nums;
                nums.clear();
                int cnt[101]={0,};
                for(int i=0;i<rsize;i++){
                    cnt[arr[i][j]]++;
                }
                for(int c=1;c<=100;c++){
                    if(cnt[c]>0){
                        nums.push_back({cnt[c],c});
                    }
                }
                sort(nums.begin(),nums.end());
                int idx = 0;
                for(auto pair:nums){
                    if(idx>=99) break;
                    arr[idx++][j] = pair.second;
                    arr[idx++][j] = pair.first;
                }
                rsize = max(rsize, idx);
                for(;idx<100;idx++){
                    arr[idx][j]=0;
                }
            }
        }
    }
    return -1;

}

int main(){
    freopen("input.txt","r",stdin);
    cin>>R>>C>>K;
    R--;
    C--;

    for(int i=0;i<3;i++){
        for(int j=0;j<3;j++){
            cin>>arr[i][j];
        }
    }

    cout<<solve();

    return 0;
}