[백준 17140] 이차원 배열과 연산 (C++)

문제

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

 

풀이

생각보다 index가 꼬여서 햇갈린문제

다음과 같이 했다

R연산의 경우

각 행마다 R연산을 실행  했으며, vector에 빈도 , 숫자 이 순서로 push_back해주었다.

각 숫자의 빈도를 counting 하고, vector에 push, sort를 하면 순서가 맞는다.

그리고는 arr에 전달하는 과정이다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int R, C, K;
int row_count = 3;
int col_count = 3;
int arr[200][200];
int num_count[101];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> R >> C >> K;
    for (int i = 1; i <= 3; i++) 
        for (int j = 1; j <= 3; j++) 
            cin >> arr[i][j];
    int time = 0;
    while (1) {
        if (time > 100) {
            cout << -1 << endl;
            return 0;
        }
        if (arr[R][C] == K) {
            cout << time << endl;
            return 0;
        }
        else if (row_count >= col_count) {
            // 연산 R
            int max_size = 0;
            for (int i = 1; i <= row_count; i++) {
                vector<pair<int, int>> vec;
                memset(num_count, 0, sizeof(num_count));
                for (int j = 1; j <= col_count; j++)
                    num_count[arr[i][j]]++;
                for (int j = 1; j <= 100; j++) {
                    if (num_count[j] == 0) {
                        continue;
                    }
                    vec.push_back(make_pair(num_count[j], j));
                }
                for (int j = 1; j <= col_count; j++)
                    arr[i][j] = 0;
                sort(vec.begin(), vec.end());
                int index = 1;
                for (auto j : vec) {
                    arr[i][index++] = j.second;
                    arr[i][index++] = j.first;
                    if (index > 100)
                        break;
                }
                index--;
                max_size = max(index, max_size);
            }
            col_count = max_size;
        }
        else if (row_count < col_count) {
            // 연산 C
            int max_size = 0;
            for (int j = 1; j <= col_count; j++) {
                vector<pair<int, int>> vec;
                memset(num_count, 0, sizeof(num_count));
                for (int i = 1; i <= row_count; i++)
                    num_count[arr[i][j]]++;
                for (int i = 1; i <= 100; i++) {
                    if (num_count[i] == 0) {
                        arr[i][j] = 0;
                        continue;
                    }
                    vec.push_back(make_pair(num_count[i], i));
                }
                for (int i = 1; i <= row_count; i++)
                    arr[i][j] = 0;
                sort(vec.begin(), vec.end());
                int index = 1;
                for (auto i : vec) {
                    arr[index++][j] = i.second;
                    arr[index++][j] = i.first;
                    if (index > 100)
                        break;
                }
                index--;
                max_size = max(index, max_size);
            }
            row_count = max_size;
        }
        time++;
    }
 
}