[백준 17140번] 이차원 배열과 연산 (C/C++)

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

---

이차원 배열과 연산 문제는 빈도수 배열을 이용하여 해결할 수 있습니다.

또한 문제에서 입력이 100보다 작거나 같은 자연수가 주어지며, 행 또는 열의 크기가 100을 넘지 않기 때문에 100을 초과하는 숫자가 나올 수 없습니다.  따라서 빈도수 배열의 크기는 100 또는 101로 하면 됩니다.

 

알고리즘의 기본 틀은 아래와 같습니다. (단,  board는 2차원 배열, freq는 빈도수 배열이며, R 연산이 기준)

1. 현재 행(i)을 확인한다. 
   1.  i행의 각 열(j)을 확인하고, freq[board[i][j]]를 증가시킨다.
   2. 빈도수 배열을 순회하며 {빈도수 배열의 인덱스, 해당 인덱스의 빈도수}를 벡터에 넣는다.
   3. 벡터를 정렬 기준에 따라 정렬한다. (수의 등장 횟수가 커지는 순, 그러한 것이 여러가지면 수가 커지는 순으로 정렬)
   4. 정렬된 벡터를 다시 board에 기록한다.
2. (i + 1) 행을 확인한다. (단, 마지막 행이라면 3번을 진행한다.)
3. 마지막 행의 크기에 맞춰 나머지 부분을 0으로 채운다.

⚠️ 주의할 점

1. 빈도수 배열의 크기 (숫자 100도 빈도수 배열에 들어갈 수 있어야 함)
2. 행의 크기가 100보다 크다면, 100까지만 기록하고, 행의 크기가 최대 100이 되도록 해주어야 함.
3. 숫자 0, 빈도수가 0인 수는 무시해야 함.

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;
 
#define num first   // 숫자
#define f second    // 빈도수
 
int board[101][101];
int freq[101];  // 빈도수 배열
 
bool cmp(pair<int, int> n1, pair<int, int> n2){ // 행 또는 열의 정렬 기준
    if(n1.f == n2.f) return n1.num < n2.num;    // 빈도수가 같으면 수가 커지는 순으로
    else return n1.f < n2.f;    // 빈도수가 커지는 순으로
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int r, c, k;
    cin >> r >> c >> k;
 
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            cin >> board[i][j]; //  배열 입력 받음
 
    int row = 3, col = 3, sec = 0;   // 행/열의 개수
    while(true){
        if(board[r - 1][c - 1] == k) break; // A[r][c]의 값이 k인 경우 중단
        if(sec == 100){sec = -1; break;}   // 100초가 지나도 A[r][c] != k이면, 중단
 
        int first, second;
        if (row >= col) {first = row; second = col;} else {first = col; second = row;}
 
        vector<int> l(first);
        for(int i = 0; i < first; i++){   // 각 행 또는 열에 대해 연산을 수행
            fill(freq, freq + 101, 0);  // 빈도수 배열을 0으로 초기화
            vector<pair<int, int>> sf;  // {수, 빈도수}를 저장하기 위한 벡터
            for(int j = 0; j < second; j++) 
                if(row >= col) freq[board[i][j]]++; // 빈도수 증가
                else freq[board[j][i]]++;
            for(int j = 1; j <= 100; j++) if(freq[j] != 0) sf.push_back({j, freq[j]});   // 각각의 {수, 빈도수}를 벡터에 저장 (수/빈도수 0은 무시)
 
            sort(sf.begin(), sf.end(), cmp);    // {수, 빈도수}의 벡터를 정렬 기준에 따라 정렬
            for(int j = 0; j < sf.size() && j < 50; j++) 
                if(row >= col) {board[i][j*2] = sf[j].num; board[i][j*2 + 1] = sf[j].f;} // 벡터를 정렬하여 다시 행 또는 열에 기록 (최대 100개)
                else {board[j*2][i] = sf[j].num; board[j*2 + 1][i] = sf[j].f;}
                
            l[i] = (sf.size() >= 50) ? 100 : sf.size() * 2;   // 정렬된 행 또는 열의 크기, 크기가 100을 넘어가는 경우 나머지는 버림
        }
        
        second = *max_element(l.begin(), l.end());  // 행 또는 열의 최대 크기
        for(int i = 0; i < first; i++) // 가장 큰 행 또는 열의 크기에 맞춰 모든 행 또는 열의 나머지 부분에 0을 채움
            for(int j = l[i]; j < second; j++)
                if(row >= col) board[i][j] = 0;
                else board[j][i] = 0;
 
        if (row >= col) {col = second;} else {row = second;}  // 업데이트 된 행 또는 열의 크기를 다시 row 또는 col에 저장
 
        sec++;
    }     
 
    cout << sec;       
}

아래는 문제 풀이에 사용된 테스트 케이스입니다.

1 2 3
1 2 1
2 1 3
3 1 1 
 
1 2 3
100 100 100
100 100 100
100 100 100