[삼성SW테스트] 백준 17140번 - 이차원 배열과 연산

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

17140번: 이차원 배열과 연산

삼성 SW역량테스트 기출문제로 시뮬레이션 유형의 코딩 문제였다.

이런 문제는 다른 유형과 같이 문제를 제대로 이해하고 문제가 요구하는 조건 그대로 정확히 코딩하는 것이 중요하다.

벡터와 소팅을 활용해 문제를 풀었다.

 

회고: 벡터 범위 벗어나는 실수를 조심하자.

       머리속으로 배열 최대 범위를 짐작해서 어떤 수가 최대 몇 개 존재할 수 있는지 생각하고 코딩했다.

       (행/열 최대 100길이니까 1이 100개 -> 소팅 시 100, 1, ...)

 

#include  <iostream>
#include  <vector>
#include  <algorithm>
#define maxlen 100 
using namespace std; 
 
int A[100][100]; 
int r, c, k; 
int row = 3, col = 3; 
int main(){ 
cin >> r >> c >> k; 
for (int i = 0; i < 3; i++){ 
for (int j = 0; j < 3; j++) 
cin >> A[i][j]; 
} 
if (A[r - 1][c - 1] == k){ 
cout << 0 << '\n'; 
return 0; 
} 
 
int time = 0; 
while (1){ 
if (time > 100){ 
cout << -1 << '\n'; 
break; 
} 
time++; 
if (row >= col){ 
// 모든행 작업 
int changeNum = 0; 
for (int i = 0; i < row; i++){ 
vector<pair<int, int> > v; 
int howMany[100 + 1]; 
for (int j = 0; j < 101; j++) 
howMany[j] = 0; 
for (int j = 0; j < col; j++){ 
howMany[A[i][j]]++; 
} 
for (int j = 1; j < 101; j++){ 
if (howMany[j]) 
v.push_back(make_pair(howMany[j], j)); 
} 
sort(v.begin(), v.end()); 
int temp = 0; 
for (int j = 0; j < 100; j++) 
A[i][j] = 0; 
if (v.size() <= 50){ 
for (int j = 0; j < v.size(); j++){ 
A[i][temp] = v[j].second; 
temp++; 
A[i][temp] = v[j].first; 
temp++; 
} 
} 
else{ 
for (int j = 0; j < 50; j++){ 
A[i][temp] = v[j].second; 
temp++; 
A[i][temp] = v[j].first; 
temp++; 
} 
} 
changeNum = max(temp, changeNum); 
} 
col = changeNum; 
} 
else{ 
int changeNum = 0; 
for (int i = 0; i < col; i++){ 
// 모든열 작업 
vector<pair<int, int> > v; 
int howMany[100 + 1]; 
for (int j = 0; j < 101; j++){ 
howMany[j] = 0; 
} 
for (int r = 0; r < row; r++){ 
howMany[A[r][i]]++; 
} 
for (int j = 1; j < 101; j++){ 
if (howMany[j]) 
v.push_back(make_pair(howMany[j], j)); 
} 
sort(v.begin(), v.end()); 
for (int r = 0; r < 100; r++){ 
A[r][i] = 0; 
} 
int temp = 0; 
if (v.size() <= 50){ 
for (int r = 0; r < v.size(); r++){ 
A[temp++][i] = v[r].second; 
A[temp++][i] = v[r].first; 
} 
} 
else{ 
for (int r = 0; r < 50; r++){ 
A[temp++][i] = v[r].second; 
A[temp++][i] = v[r].first; 
} 
} 
changeNum = max(changeNum, temp); 
} 
row = changeNum; 
} 
if (A[r - 1][c - 1] == k){ 
cout << time << '\n'; 
break; 
} 
} 
return 0; 
}