[백준-삼성SW역량테스트 기출] 17140번. 이차원 배열과 연산 C++

www.acmicpc.net/problem/17140

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

 

풀이

행의 각 숫자 개수 ( rowInfo ), 열의 각 숫자 개수 ( colInfo )를 만들어서 처리해줬다.

 

만약 행을 정렬한다고 하면

 

각 행에 대해

1. rowInfo 를 vector에 옮겨주고 정렬

2. 정렬된 vector를 사용해 matrix 값 갱신

3. rowInfo 갱신

4. 최대 column size 계산

 

-> row 정렬 마치고

1. colInfo 갱신

 

map을 따로 안만들어주고, 정렬할때마다 vector를 새로 만들어주는 것도 좋을 것 같다.

 

#define MAXN 202
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
#include <fstream>
#include <map>
using namespace std;

int r, c, k;
int matrix[MAXN][MAXN];
int result = -1;
int rSize = 3, cSize = 3;
map<int, int> rowInfo[MAXN];
map<int, int> colInfo[MAXN];

void initialize() {

    //ifstream cin;
    //cin.open("testcase.txt");

    cin >> r >> c >> k;

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

            int key = matrix[i][j];
            if (rowInfo[i].find(key) != rowInfo[i].end()) {
                rowInfo[i][key] += 1;
            }
            else {
                rowInfo[i].insert({ key, 1 });
            }

            if (colInfo[j].find(key) != colInfo[j].end()) {
                colInfo[j][key] += 1;
            }
            else {
                colInfo[j].insert({ key, 1 });
            }
        }
    }

}

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

void R() {

    memset(matrix, 0, sizeof(matrix));
    cSize = -1;

    for (int i = 0; i < rSize; i++) {

        vector<pair<int, int> > v(rowInfo[i].begin(), rowInfo[i].end());
        sort(v.begin(), v.end(), cmp);
        rowInfo[i].clear();

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

        for (int j = 0; j < v.size() * 2; j++) {
            int key = matrix[i][j];
            if (rowInfo[i].find(key) != rowInfo[i].end()) {
                rowInfo[i][key] += 1;
            }
            else {
                rowInfo[i].insert({ key, 1 });
            }
        }

        cSize = max(cSize, (int)v.size() * 2);
    }

    for (int i = 0; i < cSize; i++) {
        colInfo[i].clear();
    }

    for (int i = 0; i < rSize; i++) {
        for(int j = 0; j < cSize; j++){
            int key = matrix[i][j];
            if (key != 0) {
                if (colInfo[j].find(key) != colInfo[j].end()) {
                    colInfo[j][key] += 1;
                }
                else {
                    colInfo[j].insert({ key, 1 });
                }
            }
        }
    }

}

void C() {

    memset(matrix, 0, sizeof(matrix));
    rSize = -1;

    for (int i = 0; i < cSize; i++) {

        vector<pair<int, int> > v(colInfo[i].begin(), colInfo[i].end());
        sort(v.begin(), v.end(), cmp);
        colInfo[i].clear();

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

        for (int j = 0; j < v.size() * 2; j++) {
            int key = matrix[j][i];
            if (colInfo[i].find(key) != colInfo[i].end()) {
                colInfo[i][key] += 1;
            }
            else {
                colInfo[i].insert({ key, 1 });
            }
        }

        rSize = max(rSize, (int)v.size() * 2);
    }

    for (int i = 0; i < rSize; i++) {
        rowInfo[i].clear();
    }

    for (int i = 0; i < rSize; i++) {
        for (int j = 0; j < cSize; j++) {
            int key = matrix[i][j];
            if (key != 0) {
                if (rowInfo[i].find(key) != rowInfo[i].end()) {
                    rowInfo[i][key] += 1;
                }
                else {
                    rowInfo[i].insert({ key, 1 });
                }
            }
        }
    }
}

void solve() {

    for (int t = 0; t <= 100; t++) {

        if (matrix[r - 1][c - 1] == k) {
            result = t;
            return;
        }
    
        if(rSize >= cSize) R();
        else C();

    }

    return;
}

int main()
{
    initialize();

    solve();

    cout << result << "\n";

    return 0;
}