[17140번 이차원 배열과 연산]
https://www.acmicpc.net/problem/17140
C++의 hash map 라이브러리를 처음 사용해봤다. return 타입과 정렬에서 하는 방법을 찾아보느라 시간이 꽤 걸렸다. 그래도 이렇게 C++와 한 걸음 더 친해진 것 같다. 아마도 익숙한 Java로 풀었으면 더 빨리 풀었을 것 같다.
C++에는 hash map 라이브러리가 크게 두 가지 존재한다. map과 unordered_map으로 둘의 차이점은 데이터 저장 시 정렬 여부의 유무이다.
map의 경우 데이터가 저장될 때마다 이진 트리 구조를 활용하여 key 값을 기준으로 정렬하여 저장한다.
unordered_map의 경우 이름처럼 따로 정렬하지 않고 데이터를 저장한다.
이 문제에서는 어차피 for문이 끝날 때마다 문제에서 제시한 정렬 기준을 따라 정렬해야 했기에 unordered_map을 사용하기로 했다.
map과 unordered_map의 특이한 점은 값을 .find(key)로 찾을 때, 값의 유무에 따라 리턴 타입이 달라 auto라는 타입으로 받아야 한다는 점이다. C++11 컴파일러부터 사용 가능하며 그렇지 않을 경우 이터레이터 타입으로 받아야 한다고 한다(백준 사이트에서 제출하는 컴파일러 버전이 C++17이라 이 부분에 대해서 자세히 찾아보지는 않았다). 이런 저런 문법 관련 사항을 제외하면 문제의 풀이 방법 자체는 무난했다.
풀이
1.
R의 값과 C의 값을 비교하여 연산의 종류를 결정한다.
2.
새로운 임시 2차원 배열 B[101][101]을 생성하고
1)
R 연산이라면, 첫 번째 행부터 마지막 행까지 순회하면서 2중 for문으로 모든 열을 순회하면서 0이 아닌 값을 hash map에 넣어준다. 처음 등장하는 숫자일 경우 (key,1)로 넣어주고, 기존에 존재하는 숫자일 경우 (key, count+1)로 넣어준다.
vector에 담아 unordered_map을 정해진 기준에 따라 sort 메서드로 정렬한다. 정해진 정렬 기준을 따르기 위해bool타입을 반환하는 compare 메서드를 따로 구현하고, sort 메서드의 인자로 넣어주었다.
각 행을 순회하는 동안 max 메서드를 이용하여 100이 넘지 않는 한도 내 에서 가장 길게 만들어진 열의 개수를 maxCol 변수에 저장하고, 최종적으로 C의 값에 maxCol을 대입한다.
2)
C 연산이라면, 메커니즘은 같고 행과 열을 뒤집어 연산을 진행한다.
3.
원래 배열 A에 임시 배열 B의 값을 복사한다.
4.
100초이내에 주어진 좌표의 위치에 k값이 등장하는지 확인하고, 100초가 넘으면 -1을 반환한다.
C++ 코드
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <utility> // pair
#include <tuple>
#include <stack>
#include <map>
#include <unordered_map>
#define ll long long
#define INF 1e9
using namespace std;
int ans;
int A[101][101];
int r,c,k;
int R=3, C=3;
bool found = false;
bool compare(pair<int, int>a, pair<int, int>b) {
if(a.second == b.second) {
return a.first < b.first;
} else {
return a.second < b.second;
}
}
void sol() {
int B[101][101];
memset(B, 0, sizeof(B));
if(R >= C) {
int maxCol = 0;
for(int i=1;i<=R;++i) {
unordered_map<int,int> m;
for(int j=1;j<=C;++j) {
if(A[i][j]) {
int key = A[i][j];
auto search = m.find(key);
if(search != m.end()) { // found
int count = search->second;
m.erase(key);
m.insert(make_pair(key,count+1));
} else { // not found
m.insert(make_pair(key,1));
}
}
}
vector<pair<int,int> > vec(m.begin(), m.end());
sort(vec.begin(), vec.end(), compare);
for(int j=0;j<vec.size();++j) {
auto p = vec[j];
if(2*(j+1)-1 <= 100) {
B[i][2*(j+1)-1] = p.first;
}
if(2*(j+1) <= 100) {
B[i][2*(j+1)] = p.second;
}
}
int col = m.size() * 2;
maxCol = max(min(col,100), maxCol);
}
C = maxCol;
} else {
int maxRow = 0;
for(int j=1;j<=C;++j) {
unordered_map<int,int> m;
for(int i=1;i<=R;++i) {
if(A[i][j]) {
int key = A[i][j];
auto search = m.find(key);
if(search != m.end()) {
int count = search->second;
m.erase(key);
m.insert(make_pair(key,count+1));
} else {
m.insert(make_pair(key,1));
}
}
}
vector<pair<int,int> > vec(m.begin(), m.end());
sort(vec.begin(), vec.end(), compare);
for(int i=0;i<vec.size();++i) {
auto p = vec[i];
if(2*(i+1)-1 <= 100) {
B[2*(i+1)-1][j] = p.first;
}
if(2*(i+1) <= 100) {
B[2*(i+1)][j] = p.second;
}
}
int row = m.size() * 2;
maxRow = max(min(row,100), maxRow);
}
R = maxRow;
}
copy(&B[0][0], &B[0][0]+10201, &A[0][0]);
return;
}
int main(void) {
// ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
scanf("%d%d%d", &r,&c,&k);
for(int i=1;i<=3;++i) {
scanf("%d%d%d", &A[i][1], &A[i][2], &A[i][3]);
}
for(int i=0;i<=100;++i) {
if(A[r][c] == k) {
found = true;
break;
}
sol();
ans++;
}
if(found) {
printf("%d\n", ans);
} else {
ans = -1;
printf("%d\n", ans);
}
return 0;
}실행 결과
