이차원 배열과 연산
문제 해석
A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구하는 문제입니다.
1초마다 연산이 적용됩니다.
R연산 : 배열 A의 모든 행에 대해서 정렬을 수행합니다. (행의 개수 >= 열의 개수인 경우) C연산 : 배열 A의 모든 열에 대해서 정렬을 수행합니다. (행의 개수 < 열의 개수인 경우)
정렬하기 위해서 각각의 수가 몇번 나왔는지 카운팅합니다. 그다음, 수의 등장 횟수가 커지는 순으로, 그것이 여러가지라면 수가 커지는 순으로 정렬합니다.
행 또는 열의 크기가 100을 넘어가는 경우, 나머지 정보는 버립니다.
연산시간이 100을 넘어가는 경우에는 -1을 출력합니다.
설계(20)
전형적인 시뮬레이션 문제입니다.
먼저, 행의 최대 개수와 열의 최대 개수를 구합니다.
각 연산을 수행할 때, 숫자가 나오는 개수를 카운트할 수 있도록 nums란 배열을 사용합니다.
이와 동시에 arr에 있는 정보를 지워둡니다.
나온 숫자 정보들을 vector에 {숫자 개수, 숫자}의 정보를 저장합니다.
정렬 후, vector에 있는 모든 정보들을 arr배열에 복사합니다. (단, 50개를 넘어가는 경우는 없도록 해야합니다)
시간복잡도는 연산 수행횟수(O(100))x연산해야하는 행 or 열O(N)x각 행 or 열의 연산 수행(숫자 카운팅 O(N)+정렬(O(NlogN)+arr배열에 복사O(N))) = 최악의경우 O(100xN^2logN) => 660만 정도로 시간안에 구현이 가능합니다.
구현(30)
코드
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAXN 100
using namespace std;
int arr[MAXN][MAXN];
int nums[MAXN+1];
int R,C,K;
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin >> R >> C >> K;
for (int i = 0 ;i < 3; i++){
for (int j= 0;j<3; j++){
cin >> arr[i][j];
}
}
R--;
C--;
int time = 0;
while (time<=MAXN){
if (arr[R][C] == K) {
cout << time <<"\n";
return 0;
}
// 행,열 길이
int len_r = 0;
int len_c = 0;
for (int j = 0; j < MAXN; j++){
for (int i = 0 ; i < MAXN; i++){
if (!arr[i][j]) {
if (len_r < i) len_r = i;
break;
}
}
}
for (int i = 0 ; i <MAXN; i++){
for (int j =0 ;j<MAXN; j++){
if (!arr[i][j]){
if (len_c < j){
len_c = j;
}
break;
}
}
}
//R연산
if (len_r >= len_c){
for (int i = 0 ; i < len_r; i++){
memset(nums,0,sizeof(nums));
vector<pair<int,int>> tmp_v;
for (int j= 0; j < len_c; j++){
if (!arr[i][j]) continue;
nums[arr[i][j]]++;
arr[i][j] = 0;
}
for (int j = 1 ;j <= MAXN; j++){
if (nums[j]){
tmp_v.push_back({nums[j],j});
}
}
sort(tmp_v.begin(),tmp_v.end());
int idx= 0 ;
for (int j =0 ;j < min(MAXN/2,(int)tmp_v.size()); j++){
arr[i][idx++] = tmp_v[j].second;
arr[i][idx++] = tmp_v[j].first;
}
}
}
// C연산
else{
for (int j = 0 ;j < len_c; j++){
memset(nums,0,sizeof(nums));
vector<pair<int,int>> tmp_v;
for (int i= 0; i < len_r; i++){
if (!arr[i][j]) continue;
nums[arr[i][j]]++;
arr[i][j] = 0;
}
for (int i = 1 ;i <= MAXN; i++){
if (nums[i]){
tmp_v.push_back({nums[i],i});
}
}
sort(tmp_v.begin(),tmp_v.end());
int idx= 0 ;
for (int i =0 ;i < min(MAXN/2,(int)tmp_v.size()); i++){
arr[idx++][j] = tmp_v[i].second;
arr[idx++][j] = tmp_v[i].first;
}
}
}
time++;
}
cout <<"-1\n";
return 0;
}
디버깅
nums정보를 vector에 담을 때,범위 실수로 숫자 100에 대한 정보를 저장하지 않는 오류를 범했습니다.
제출결과
0 ms
마무리
전형적인 시뮬레이션 문제였습니다.
벡터를 사용하지 않고 최적화해보려는 시도로 인해 시간이 오래걸렸습니다.
벡터를 사용하지 않고, fill함수로 INF값으로 초기화 한 후, 정렬하는 방식으로 구현을 시도했으나 더 느린 결과가 나왔습니다.
fill함수는 loop문을 도는 함수여서 memset보다 더 느린 것 같습니다.