BOJ
BOJ::17140 이차원 배열과 연산
BOJ Gold 4
BOJ::17140 이차원 배열과 연산
- Link : BOJ::17140
- Level : Gold 4
- tag : implementation, simulation
시사점
- 재밌는 구현 문제입니다.
- 구현문제답게 신경써야할 부분이 조금 있습니다.
이해(3)
- 3 * 3 행렬이 주어집니다.
- if( 최대 행의 값 >= 최대 열의 값 )
- 행에 대한 “정렬”
- else
- 열에 대한 “정렬”
- 위와 같이 정렬을 진행합니다.
- 정렬은 다음과 같은 작업을 의미합니다.
- 해당 행 혹은 열에 (1, 2, 2)가 있는 경우 다음과 같이 정렬될 수 있습니다.
- 1이 1번, 2가 2번 나오므로 -> (1, 1, 2, 2)
- 정렬된 결과를 다시 행/열에 대입하여야 합니다.
- 이때 다음과 같은 우선순위로 대입 순서를 나눕니다.
- 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지라면 수가 커지는 순으로 정렬한다.
설계, 손 코딩(5)
- 손으로 중심이 되는 코드를 구현합니다.
- 행과 열에 대해 같은 “정렬”을 적용하기 위해 정렬행위를 하는 함수 하나를 떼어내서 만들어줍니다.
- 따라서, process 함수에서는 전체를 관리하고,
- sort 함수에서는 해당 정렬과정에만 집중할 수 있게 합니다.
- 신경써야 할 부분은 다음과 같습니다.
- 최대 100회 돌려도 답이 나오지 않는 경우 -1 출력
- 연산의 결과에 따라서, 해당 행의 길이가 늘어날 수 있음
- 최대 사이즈 100까지만 허용가능
복잡도
- O(100회) * O(N^2)
구현(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)
- 2가지 실수를 하였습니다.
- (3m) : 최대 행/열의 사이즈를 sort함수에서 갱신해줍니다.
- 이때, pq의 사이즈로 갱신하였습니다.
- 실제로는, pq의 사이즈 * 2 로 해주어야 합니다.
- (5m) : 행 연산에 대해서는 line[j]에 값을 복사해주고,
- 열 연산에 대해서는 line[i]에 값을 복사해주어야 하지만,
- 후자를 j에 대입하였습니다.
- (3m) : 최대 행/열의 사이즈를 sort함수에서 갱신해줍니다.