[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가 되기 위한 최소 시간을 구해보자.

 

이 문제는, 삼성코딩테스트 상반기에 제출되었던 문제라고 한다. 삼성코딩테스트를 준비하시는 분들은 최대 1시간 30분안에 문제를 푸는 것을 추천한다.

 

문제접근법.

 

1. 숫자가 등장하는 것을 저장하는 자료구조가 필요하다.

2. 저장된 숫자들을 문제에서 제시한 비교 조건에 따라서 배열에 채워야 한다.

3. 행 또는 열의 크기가 100을 넘어가는 경우에 대해서 처리한다.

 

 숫자가 등장하는 것을 저장하기 위해서 MAP 자료구조를 이용했다. MAP 자료구조를 사용하면 손 쉽게 숫자의 등장을 파악할 수 있고, 나중에 큐에 넣기에도 적절하다. 큐는 우선순위 큐를 사용해서 특정 조건에 따라서 정렬될 수 있도록 했다.

 

 문제에서 제시한 조건에 따르면, 등장 횟수가 오름 차순 순이어야 하고, 등장 횟수가 같으면 숫자가 오름 차순이 되어야 한다. 오름 차순이 되어야 한다는 것은 작은 숫자부터 먼저 큐에서 Pop되어야 한다.

 

 문제의 예제를 통해서 살펴본다.

 

1 2 1 → (2, 1), (1, 2) → 2 1 1 2

2 1 3 → (1, 1), (2, 1), (3, 1) → 1 1 2 1 3 1

3 3 3 → (3, 3) → 3 3

 

 문제의 예시를 이해하고 우선순위 큐를 선언할 때 비교 함수를 가진 구조체를 선언해서 넣어주도록 한다.

 

해설코드(C++).

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
#include <queue>
using namespace std;
 
int r, c, k;
int A[101][101];
int time = 0;
int r_cnt = 3;
int c_cnt = 3;
 
typedef struct item {
    int num;
    int cnt;
    item(int _n, int _c) : num(_n), cnt(_c) {};
}item;
 
typedef struct myfunc {
    bool operator()(item i1, item i2) {
        if (i1.cnt == i2.cnt) {
            return i1.num > i2.num;
        }
        return i1.cnt > i2.cnt;
    }
}myfunc;
 
priority_queue<item, vector<item>, myfunc> p_q;
int main(void) {
    freopen("input.txt", "r", stdin);
    memset(A, 0, sizeof(A));
    cin >> r >> c >> k;
 
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            cin >> A[i][j];
        }
    }
    
    while (time <= 100) {
        // Exit
        if (A[r][c] == k)
            break;
        time += 1;
 
        // R Oper
        if (r_cnt >= c_cnt)
        {
            int t_c_idx = 0;
            for (int i = 1; i <= r_cnt; i++) {
                map<int, int, less<int>> m;
                map<int, int, less<int>>::iterator itr;
                for (int j = 1; j <= c_cnt; j++) {
                    if (A[i][j] == 0)
                        continue;
 
                    if (m.find(A[i][j]) == m.end()) 
                        m[A[i][j]] = 1;
                    else
                        m[A[i][j]] += 1;
                }
                
                // Change
                int c_idx = 1;
                for (int j = 1; j <= c_cnt; j++) A[i][j] = 0;
 
                while (!p_q.empty()) p_q.pop();
                for (itr = m.begin(); itr != m.end(); itr++) {
                    p_q.push(item((*itr).first, (*itr).second));
                }
 
                while (!p_q.empty()) {
                    A[i][c_idx] = p_q.top().num;
                    A[i][c_idx + 1] = p_q.top().cnt;
 
                    if (c_idx + 1 == 100)
                        break;
                    c_idx += 2;
                    p_q.pop();
                }
                t_c_idx = max(t_c_idx, c_idx - 1);
            }
            c_cnt = t_c_idx;
        }
        // C Oper
        else {
            int t_r_idx = 0;
            for (int i = 1; i <= c_cnt; i++) {
                map<int, int, less<int>> m;
                map<int, int, less<int>>::iterator itr;
                for (int j = 1; j <= r_cnt; j++) {
                    if (A[j][i] == 0)
                        continue;
 
                    if (m.find(A[j][i]) == m.end())
                        m[A[j][i]] = 1;
                    else
                        m[A[j][i]] += 1;
                }
 
                // Change
                int r_idx = 1;
                for (int j = 1; j <= r_cnt; j++) A[j][i] = 0;
 
                while (!p_q.empty()) p_q.pop();
                for (itr = m.begin(); itr != m.end(); itr++) {
                    p_q.push(item((*itr).first, (*itr).second));
                }
 
                while (!p_q.empty()) {
                    A[r_idx][i] = p_q.top().num;
                    A[r_idx + 1][i] = p_q.top().cnt;
 
                    if (r_idx + 1 == 100)
                        break;
                    r_idx += 2;
                    p_q.pop();
                }
                t_r_idx = max(t_r_idx, r_idx - 1);
            }
            r_cnt = t_r_idx;
        }
    }
 
    if (time > 100)
        time = -1;
 
    cout << time << endl;
    return 0;
}