백준[17140] 이차원 배열과 연산

문제 출처 : https://www.acmicpc.net/problem/17140

 

위 문제는 '삼성 역량 테스트' 기출문제로 분류되어 있다.

 

먼저 다른 사람의 코드는 보지 못했다. 필자는 문제를 읽으면서 그냥 하라는 대로 구현하는 문제로 생각하고 시키는대로 풀었다.

 

언제나 그렇듯 설계를 잘하고 코드를 짜면서 제대로 돌아가고 있는지 확인하는 과정이 필요하다. 이번에도 확인하면서 잘 돌아가는것을 보았으나 한두개의 일부분만을 확인했지 10번 20번 돌아가는 경우의 검증을 제대로 하지 않아서 오류를 찾는데 시간이 좀 걸렸다. 이제 문제를 풀어보자.

 

3x3 matrix를 기준으로 R연산 혹은 C연산을 하는 문제이다. 연산을 구현하기 위해서는 각 Row, Collum 마다의 값과 횟수를 기준으로 정렬하는 방법이 필요하다. 여기서 필자는 map, vector 등의 컨테이너로 시도를 했는데 횟수와 커지는 수의 2가지 조건을 가지고 정렬하기 때문에 결국은 operator 연산으로 사용자 정의함수를 사용해 정렬해야 함을 알고 사용할 줄 아는 구조체 정렬을 사용했다.

 

구조체를 정의하고 vector<'구조체'> 형으로 값과 나온 횟수를 벡터에 저장하여 정렬을 하였다.

이후, 문제에서 요구하는 방법으로 각 정렬한 값들을 2차원 배열에 저장하여 문제를 해결하였다. 나온 횟수는 횟수를 저장하는 배열을 새로 선언하여 각 Row 혹은 Collum 을 행할때마다 사용하였다. 

 

R연산에만 간단하게 주석으로 표시하겠다. 코드는 아래와 같다.

 

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<math.h>
#include<algorithm>
#include<stack>
#include<queue>
#include<set>
#include<iterator>
#include<deque>
#include<map>
 
using namespace std;
 
int r, c, k,arr[110][110],Map[110][110],ans;
vector<int> arr2[110];
int lenR = 3, lenC = 3;
 
struct info
{
    int val = 0, cnt = 0;
};
 
bool cmp(info a, info b) {
    if (a.cnt == b.cnt) return a.val < b.val;
    else return a.cnt < b.cnt;
}
 
void R(int a,int b) {
    memset(arr, 0, sizeof(arr));
    for (int i = 0; i < a; i++) {
        vector<info> v;
        info in;
        int num[110] = { 0 };   //각 숫자의 등장횟수를 저장할 변수
        for (int j = 0; j < b; j++) {
            if (Map[i][j] == 0) continue;
            num[Map[i][j]]++; // 각 행에서 숫자의 개수를 저장
        }
        for (int j = 1; j <= 100; j++) {
            if (num[j] != 0) {
                in.val = j;
                in.cnt = num[j];  //num[j]의 값이 있는것은 그 숫자가 있다는 뜻
                v.push_back(in);  // val : 해당 숫자의 값, cnt는 등장 횟수  이 자료를 push
            }
        }
        sort(v.begin(), v.end(),cmp); // 문제의 요구조건에 맞게 정렬
 
        for (int j = 0,k=0; j < v.size(); j++,k=k+2) {
            if (j >= 50) break;
            arr[i][k] = v[j].val;
            arr[i][k+1] = v[j].cnt;
        } // vector 는 (값, 횟수) 로 저장되어 있다. 문제의 예시로  [3, 1, 1] 의 경우 벡터 v[0] = {3,1} v[1] = {1,2} 이다. 
          // 이것을 [3 1 1 2] 로 만들기 위해 위와같이 해결
        int l = v.size()*2;
        lenC = max(lenC, l);  // 길이가 변화된 배열을 위해 최대값을 뽑아냄
    }
    for (int i = 0; i < lenR; i++) {
        for (int j = 0; j < lenC; j++) {
            Map[i][j] = arr[i][j];
        }
    }
    // 배열을 만들어줌
 
}
void C(int a,int b) {
    memset(arr, 0, sizeof(arr));
    for (int i = 0; i < b; i++) {
        vector<info> v;
        info in;
        int num[110] = { 0 };
        for (int j = 0; j < a; j++) {
            if (Map[j][i] == 0) continue;
            num[Map[j][i]]++;
        }
        for (int j = 1; j <= 100; j++) {
            if (num[j] != 0) {
                in.val = j;
                in.cnt = num[j];
                v.push_back(in);
            }
        }
        sort(v.begin(), v.end(), cmp);
 
        for (int j = 0, k = 0; j < v.size(); j++, k = k + 2) {
            if (j >= 50) break;
            arr[k][i] = v[j].val;
            arr[k+1][i] = v[j].cnt;
        }
        
        int l = v.size() * 2;
        lenR = max(lenR, l);
    }
    for (int i = 0; i < lenR; i++) {
        for (int j = 0; j < lenC; j++) {
            Map[i][j] = arr[i][j];
        }
    }
 
}
 
int main()
{
    cin >> r >> c >> k;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            scanf("%d", &Map[i][j]);
            arr[i][j] = Map[i][j];
        }
    }
    for(int i=0;i<=100;i++) {
        //cout << lenR << "  " << lenC << endl;
        if (arr[r - 1][c - 1] == k) break;
        ans++;
        if (ans > 100) break;
        if (lenR >= lenC) R(lenR,lenC);
        else C(lenR,lenC);
    }
    if (ans > 100) printf("-1");
    else printf("%d", ans);
    return 0;
}