[백준] 17140 이차원 배열과 연산

17140번: 이차원 배열과 연산

문제 확인

 

해시를 이용한 구현 문제입니다.

 

풀이

 

문제의 두 연산을 구분하기 위해 행, 열의 최대 길이를 미리 기록 해 둡니다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

연산에서 해당 수, 수가 등장한 횟수 모두 알아야 하므로 hash를 사용하여 간단하게 풀 수 있습니다. unordered_map을 사용하여 풀 수 있지만 이를 직접 정렬은 불가능하며 vector로 변환한 후 정렬하여 풀 수 있습니다.

 

R연산의 경우 각 행에서 등장한 원소들을 등장 횟수와 함께 기록하고 C 연산의 경우 열에서 원소, 등장 횟수를 기록하고 이를 등장 횟수 기준으로 정렬한 후 존재하는 원소만을 기록합니다.

기록하면서 행, 열의 최댓값을 구하고 이를 기록하여 다음 연산에 사용합니다.

 

코드

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef struct pir {
    int idx, cnt;
}pir;
 
int main() {
    int r, c, k;
    scanf("%d%d%d", &r, &c, &k);
    r--, c--;
    int ary[100][100] = { 0 };
    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            scanf("%d", &ary[i][j]);
 
    int mx_x = 3, mx_y = 3, t = 0;
 
    pir hsh[100][101];
 
    while (t <= 100 && ary[r][c] != k) {
        memset(hsh, 0, sizeof hsh);
        if (mx_x >= mx_y) {//R연산
            
            for (int i = 0; i < mx_x; i++) {
                for (int j = 0; j < mx_y; j++) {
                    if (ary[i][j]) {//0 제외
                        hsh[i][ary[i][j]].idx = ary[i][j];//등장한 수 기록
                        ++hsh[i][ary[i][j]].cnt;//횟수 기록
                    }
                }
            }
 
            memset(ary, 0, sizeof ary);
            for(int i=0;i<mx_x;i++)
            sort(hsh[i], hsh[i] + 101, [](const pir &a, const pir &b)->bool {
                if (!a.idx) return false;//0의 경우 등장하지 않거나 0 값이므로 고려하지 않음
                if (!b.idx) return true;
                if (a.cnt != b.cnt)return a.cnt < b.cnt;//등장횟수 비교
                return a.idx < b.idx;//횟수가 같은 경우 수를 비교
            });
 
            int ty = 0;
            for (int i = 0; i < mx_x; i++) {
                int cur = 0;
                while (cur < 50 && hsh[i][cur].idx) {//결과를 저장
                    ary[i][cur * 2] = hsh[i][cur].idx;
                    ary[i][cur * 2 | 1] = hsh[i][cur].cnt;
                    cur++;
                }
                ty = ty < cur ? cur : ty;
            }
            mx_y = ty*2;//변경된 열 길이 반영
 
        }
        else {//C연산
            for (int i = 0; i < mx_y; i++) {
                for (int j = 0; j < mx_x; j++) {
                    if (ary[j][i]) {
                        hsh[i][ary[j][i]].idx = ary[j][i];
                        ++hsh[i][ary[j][i]].cnt;
                    }
                }
            }
 
            memset(ary, 0, sizeof ary);
            for (int i = 0; i < mx_y; i++)
                sort(hsh[i], hsh[i] + 101, [](const pir &a, const pir &b)->bool {
                if (!a.idx) return false;
                if (!b.idx) return true;
                if (a.cnt != b.cnt)return a.cnt < b.cnt;
                return a.idx < b.idx;
            });
 
            int tx = 0;
            for (int i = 0; i < mx_y; i++) {
                int cur = 0;
                while (cur < 50 && hsh[i][cur].idx) {
                    ary[cur * 2][i] = hsh[i][cur].idx;
                    ary[cur * 2 | 1][i] = hsh[i][cur].cnt;
                    cur++;
                }
                tx = tx < cur ? cur : tx;
            }
            mx_x = tx*2;
        }
 
        t++;
    }
    printf("%d", t > 100 ? -1 : t);
}