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

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

열이든 행이든 연산 하나를 제대로 구현하면, 나머지 하나는 똑같다.

보통 개수를 셀 때, cnt[m[i]]++ 이런 방식으로 세는데, 이 경우에는 1회 이상 등장한 숫자의 개수도 함께 필요하고,

이 수들의 빈도와 수 자체를 가지고 정렬을 해야하기 때문에 다른 방식을 사용했다.

먼저 map을 사용해서 숫자별 개수를 기록했다. 이후에 벡터에 pair 형태로 옮기면서 정렬했다.

주의할 것이, 중간에 R연산을 할 때는 열의 길이가 갱신되고, C연산을 할 때는 행의 길이가 갱신되는데, 따라서 연산을 시작할 당시의 값으로 반복문의 범위를 잡아줘야, 중간에 반복문의 범위가 바뀌는 것을 방지할 수 있다.

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
 
using namespace std;
typedef pair<int, int> pii;
 
int r, c, k, m[101][101], cnt[101], rnum = 3, cnum = 3;
map<int, int> mp;
vector<pii> v;
 
bool cmp(pii a, pii b) {
    if (a.second < b.second) return true;
    else if (a.second == b.second) {
        return a.first < b.first;
    }
    else return false;
}
 
void rOpr() {
    int curC = cnum; //연산 중간에 행길이를 갱신할 것이기 때문에 시작값 저장
    for (int i = 1; i <= rnum; i++) {
        for (int j = 1; j <= curC; j++) {
            if (m[i][j] == 0) continue;
            mp[m[i][j]]++;
        }
        
        for (map<int, int>::iterator itr = mp.begin(); itr != mp.end(); itr++)
            v.push_back({ itr->first, itr->second });
 
        sort(v.begin(), v.end(), cmp);
 
        int vSize = v.size();
        if (v.size() >= 50) vSize = 50; //100개까지만 취하도록
        for (int j = 0; j < vSize; j++) {
            m[i][2*j+1] = v[j].first;
            m[i][2*j+2] = v[j].second;
        }
        
        for (int j = vSize * 2 + 1; j <= curC; j++)
            m[i][j] = 0; // 원래 길이보다 짧아지면, 이전 것을 0으로 만들어줘야 함
 
        if (cnum < vSize * 2) cnum = vSize * 2; //최대 길이 갱신
        
        mp.clear();
        v.clear();
    
    }
}
 
void cOpr() {
    int curR = rnum;
    for (int i = 1; i <= cnum; i++) {
        for (int j = 1; j <= curR; j++) {
            if (m[j][i] == 0) continue;
            mp[m[j][i]]++;
        }
 
        for (map<int, int>::iterator itr = mp.begin(); itr != mp.end(); itr++)
            v.push_back({ itr->first, itr->second });
 
        sort(v.begin(), v.end(), cmp);
 
        int vSize = v.size();
        if (v.size() >= 50) vSize = 50;
        for (int j = 0; j < vSize; j++) {
            m[2 * j + 1][i] = v[j].first;
            m[2 * j + 2][i] = v[j].second;
        }
 
        for (int j = vSize * 2 + 1; j <= curR; j++)
            m[j][i] = 0;
 
        if (rnum < vSize * 2) rnum = vSize * 2;
 
        mp.clear();
        v.clear();
 
    }
}
int main(void) {
    cin >> r >> c >> k;
    for (int i = 1; i <= 3; i++)
        for (int j = 1; j <= 3; j++)
            cin >> m[i][j];
 
    int time = 0;
    for (time = 0; time <= 100; time++) {
    
        if (m[r][c] == k) break; //종료 조건
        if (rnum >= cnum)  //r연산
            rOpr();
        
        else 
            cOpr();
    }
 
    if (time == 101) cout << -1;
    else cout << time;
 
    return 0;
}