BOJ::17140 이차원 배열과 연산

시사점

이해(3)

설계, 손 코딩(5)

복잡도

구현(11)

#include<bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define r_rep(i,a,b) for(int i=a;i>b;i--)
const int MAXNM  = 100+1;
enum RC{ROW=0, COLUMN=1};
using namespace std;
int n = 3, m = 3;
int ex, ey, findk;
int a[MAXNM][MAXNM];
struct cell{int num; int cnts;
    bool operator<(const struct cell& t)const{
        if(cnts == t.cnts){
            return num > t.num;
        }else return cnts > t.cnts;
    }
};
void input(){
    cin >> ex >> ey >> findk;
    ex -= 1, ey -= 1;
    rep(i, 0, n) rep(j, 0, m) cin >> a[i][j];
}

void _sort(int th, bool which, int cur, int &next, int (&line)[MAXNM]){
    int cnt[MAXNM] = {0,};
    priority_queue<cell> pq;
    rep(i, 0, cur) cnt[line[i]]++;
    rep(i, 1, 100+1) if(cnt[i]) pq.push({i, cnt[i]});
    next = max(next, min((int) pq.size() * 2, 100)); //실수(3m) : *2안해줌
    if(which == ROW){
        int j = 0;
        while(!pq.empty()){
            a[th][j++] = pq.top().num;
            a[th][j++] = pq.top().cnts;
            pq.pop();
            if(j == 100) break;
        }
    }else{
        int i = 0;
        while(!pq.empty()){
            a[i++][th] = pq.top().num;
            a[i++][th] = pq.top().cnts;
            pq.pop();
            if(i == 100) break;
        }
    }
}
void process(){
    input();
    int time = 0;
    while(true){
        int nextn = n, nextm = m;
        if(a[ex][ey] == findk) break;
        // -->
        if(n >= m){
            rep(i, 0, n){
                int line[MAXNM];
                rep(j, 0, m){ line[j] = a[i][j]; a[i][j] = 0;}
                _sort(i, ROW, m, nextm, line);
            }
        // C
        }else{
            rep(j, 0, m){
                int line[MAXNM];
                rep(i, 0, n){ line[i] = a[i][j]; a[i][j] = 0;} // 실수(5m) : line[j]에 대입
                _sort(j, COLUMN, n, nextn, line);
            }
        }
        n = max(n, nextn); m = max(m, nextm);
        time++;
        if(time > 100){
            cout << "-1" << endl;
            return;
        }
    }
    cout << time << endl;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    process();
    return 0;
}

디버깅(7)

좋은 코드

최적화