[BAEKJOON] 17140. 이차원 배열과 연산

Posted on April 21, 2021

문제 :

크기가 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보다 작거나 같은 자연수이다.

출력 :

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

풀이 :

우선 본 문제는 열 단위 정렬도 있다 보니, 배열 초기화 혹은 정렬 과정에서 실수가 발생하기 매우 좋은 문제인 듯 하다.

초기화, 업데이트가 매우 중요한 문제

초기화, 업데이트를 적시에 잘 시행해주어야 하며 매 과정마다 빼먹지 않고 해주어야 하기 때문에 실수가 발생하기 쉬운듯 하다

우선 현재 최대 열 길이, 최대 행 길이를 적시에 잘 업데이트 해주어야 한다.

또 현재 행 또는 열의 숫자들을 카운트하는 counts[100] 배열의 경우에도 매 반복문 마다 초기화를 반드시 해주어야 한다.

정렬된 배열인 mapary의 경우에도 특정 행 또는 열의 길이가 매번 고정되거나 늘어나기만 하는 것이 아니기 때문에 전 반복문에서 기록되어있던 값들은 적시에 잘 초기화를 해주어야 한다. 사실 말이 쉽지… 디버깅을 계속 진행해주면서 초기화해주어야 할 부분들을 지속적으로 찾아낸 것 같다.
행 정렬은 생각하기 쉬운데, 열 정렬은 어렵다?

꼭 그렇지만은 않다. 본 문제를 첨을 이해했을 때에는 어떻게 열 정렬을 진행해주어야 하나 감이 오지 않았지만, 문제 내용을 잘 살펴보면 친절하게도 배열의 최대 크기를 행, 열 모두 100 이하로 정확히 제한을 두고 있다. 따라서 배열 크기를 고정하고 매번 열, 행에 인덱스로 접근하여 정렬을 진행해주면 된다.

코드 :

코드 보기/접기

#include <iostream>
#include <cstring>
#include <queue>
#include <utility>
#include <algorithm>

#define pii pair<int, int>

using namespace std;
int currows = 3, curcols = 3;
int mapary[100][100], counts[101];

void oneSortProcess() {
    priority_queue<pii, vector<pii >, greater<>> pq;

    if (currows >= curcols) {
        int maxcols = 0;
        for (int i = 0; i < currows; i++) {
            memset(counts, 0, sizeof(counts));
            for (int j = 0; j < curcols; j++)
                counts[mapary[i][j]]++;

            for (int k = 1; k < 101; k++)
                if (counts[k]) pq.push(pii(counts[k], k));

            int curidx = 0;
            while (!pq.empty()) {
                mapary[i][curidx++] = pq.top().second;
                mapary[i][curidx++] = pq.top().first;
                pq.pop();
                if (curidx >= 100) break;
            }
            for (int k = curidx; k < curcols; k++)
                mapary[i][k] = 0;
            maxcols = max(maxcols, curidx);
        }
        curcols = maxcols;
    } else {
        int maxrows = 0;
        for (int i = 0; i < curcols; i++) {
            memset(counts, 0, sizeof(counts));
            for (int j = 0; j < currows; j++)
                counts[mapary[j][i]]++;

            for (int k = 1; k < 101; k++)
                if (counts[k]) pq.push(pii(counts[k], k));

            int curidx = 0;
            while (!pq.empty()) {
                mapary[curidx++][i] = pq.top().second;
                mapary[curidx++][i] = pq.top().first;
                pq.pop();
                if (curidx >= 100) break;
            }
            for (int k = curidx; k < currows; k++)
                mapary[k][i] = 0;
            maxrows = max(maxrows, curidx);
        }
        currows = maxrows;
    }
}

int main() {
    int goalrow, goalcol, goalnum;
    cin >> goalrow >> goalcol >> goalnum;

    goalrow--;
    goalcol--;
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cin >> mapary[i][j];

    for (int i = 0; i < 101; i++) {
        if (mapary[goalrow][goalcol] == goalnum) {
            cout << i << '\n';
            return 0;
        }
        oneSortProcess();
    }
    cout << "-1\n";
    return 0;
}

Algorithm

algorithm baekjoon C++