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

 

풀이

- R 연산, C 연산 각각 구현

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int R, C, K;
int rowSize = 3, colSize = 3;
int matrix[100][100];

void operationR() {
    int maxLen = 0;
    for(int row=0; row<rowSize; row++) {
        unordered_map<int, int> freq;
        for(int i = 0; i < colSize; i++)
            if(matrix[row][i])
                freq[matrix[row][i]]++;
        
        vector<pair<int, int>> v;
        for(const auto &[n, f]:freq) v.push_back({ f, n });
        sort(v.begin(), v.end());

        int len = 0;
        for(const auto &[f, n]:v) {
            matrix[row][len++] = n;
            matrix[row][len++] = f;
        }

        for(int i=len; i<colSize; i++) matrix[row][i] = 0;
        maxLen = max(maxLen, len);
    }
    colSize = maxLen;
}
void operationC() {
    int maxLen = 0;
    for(int col=0; col<colSize; col++) {
        unordered_map<int, int> freq;
        for(int i = 0; i < rowSize; i++)
            if(matrix[i][col])
                freq[matrix[i][col]]++;
        
        vector<pair<int, int>> v;
        for(const auto &[n, f]:freq) v.push_back({ f, n });
        sort(v.begin(), v.end());

        int len = 0;
        for(const auto &[f, n]:v) {
            matrix[len++][col] = n;
            matrix[len++][col] = f;
        }

        for(int i=len; i<rowSize; i++) matrix[i][col] = 0;
        maxLen = max(maxLen, len);
    }
    rowSize = maxLen;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> R >> C >> K;
    R--; C--; // 0-based
    for(int i=0; i<rowSize; i++)
        for(int j=0; j<colSize; j++)
            cin >> matrix[i][j];

    int sec = 0;
    while(matrix[R][C] != K and ++sec <= 100) {
        if(rowSize < colSize) operationC();
        else operationR();
    }
    cout << (sec > 100 ? -1 : sec);
}

 

`operationR()` 함수의 실행 순서는 다음과 같다.

• 각 행마다 R 연산을 수행한다.(`for(int row=0; row<rowSize; row++)`)
  • 0이 아닌 값에 대하여 빈도 계산(`freq`)
  • 빈도, 수를 우선순위로 오른차순 정렬(`pair<freq, val>`을 이용한 `sort()`)
  • `matrix[row][]`에 수, 빈도 순으로 대입
  • 열이 줄어들었다면 쓰레기값 0으로 초기화
• 가장 긴 행의 크기로 열 크기 변경(`colSize = maxLen`)

 

- 대칭변환

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int R, C, K;
int rowSize = 3, colSize = 3;
int matrix[100][100];

void transpose() {
    int mx = max(rowSize, colSize);
    for(int i=0; i<mx; i++)
        for(int j=i+1; j<mx; j++)
            swap(matrix[i][j], matrix[j][i]);
    swap(rowSize, colSize);
}
void operateR() {
    int maxLen = 0;
    for(int row=0; row<rowSize; row++) {
        unordered_map<int, int> freq;
        for(int i = 0; i < colSize; i++)
            if(matrix[row][i])
                freq[matrix[row][i]]++;
        
        vector<pair<int, int>> v;
        for(const auto [n, f]:freq)
            v.push_back({ f, n });
        sort(v.begin(), v.end());

        int len = 0;
        for(const auto [f, n]:v) {
            matrix[row][len++] = n;
            matrix[row][len++] = f;
        }

        for(int i=len; i<colSize; i++) matrix[row][i] = 0;
        maxLen = max(maxLen, len);
    }
    colSize = maxLen;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> R >> C >> K;
    R--; C--; // 0-based
    for(int i=0; i<rowSize; i++)
        for(int j=0; j<colSize; j++)
            cin >> matrix[i][j];
    
    int sec = 0;
    while(matrix[R][C] != K and ++sec <= 100) {
        bool transposed = false;
        if(rowSize < colSize) {
            transpose();
            transposed = true;
        }
        operateR();
        
        if(transposed) transpose();
    }
    cout << (sec > 100 ? -1 : sec);
}

 

행과 열에 대해 같은 연산을 수행할 때 2차원 배열의 인덱스 순서 때문에 하나의 함수로 처리하기 힘들다.

이때 2차원 배열을 y = x에 대해 대칭 변환하여 하나의 함수로 처리할 수 있다. (`transpose()`)