(백준 c++)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초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

 

 

 

 

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

using namespace std;

bool asc(pair<int, int> a, pair<int, int> b){
    if(a.second == b.second){
        return a.first < b.first;
    }
    return a.second < b.second;
}

int main(void){
    int r, c, k, count = 0;
    int rowCount = 3, colCount = 3;
    vector<vector<int>> matrix(100, vector<int>(100, 0));

    cin >> r >> c >> k;

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

    while(count++ <= 100){
        if(matrix[r - 1][c - 1] == k){
            cout << count - 1;
            return 0;
        }

        if(rowCount >= colCount){
            for(int i = 0; i < rowCount; i++){
                vector<pair<int, int>> tmpArr;
                map<int, int> m;
                int index = 0;
                
                for(int j = 0; j < 100; j++){
                    if(matrix[i][j] > 0){
                        m[matrix[i][j]]++;
                    }
                }

                for(auto itr = m.begin(); itr != m.end(); itr++){
                    tmpArr.push_back({itr->first, itr->second});
                }

                sort(tmpArr.begin(), tmpArr.end(), asc);

                for(int j = 0; j < tmpArr.size(); j++){
                    matrix[i][index++] = tmpArr[j].first;
                    matrix[i][index++] = tmpArr[j].second;
                }
                
                for(int j = tmpArr.size() * 2; j < 100; j++){
                	matrix[i][index++] = 0;
                }

                colCount = colCount < tmpArr.size() * 2 ? tmpArr.size() * 2 : colCount;
            }
        }
        else{
            for(int i = 0; i < colCount; i++){
                vector<pair<int, int>> tmpArr;
                map<int, int> m;
                int index = 0;
                
                for(int j = 0; j < 100; j++){
                    if(matrix[j][i] > 0){
                        m[matrix[j][i]]++;
                    }
                }

                for(auto itr = m.begin(); itr != m.end(); itr++){
                    tmpArr.push_back({itr->first, itr->second});
                }

                sort(tmpArr.begin(), tmpArr.end(), asc);
				
                for(int j = 0; j < tmpArr.size(); j++){
                    matrix[index++][i] = tmpArr[j].first;
                    matrix[index++][i] = tmpArr[j].second;
                }
                
                for(int j = tmpArr.size() * 2; j < 100; j++){
                	matrix[index++][i] = 0;	
                }

                rowCount = rowCount < tmpArr.size() * 2 ? tmpArr.size() * 2 : rowCount;
            }
        }
    }

    cout << -1;

    return 0;
}