[백준]이차원배열과 계산

문제를 잘 이해해서 푸는 시뮬레이션 문제였다.

일단 문제의 해결방안은 다음과 같다.

1.숫자들의 빈도를 어떻게 셀것인가 ?

2.여러가지 우선순위들이 존재한다. --> 정렬을 한다.

3.A[][] 에 잘 넣어준다. 최대 행, 열의 길이를 잘 측정한다.

문제에 실수를 했던 부분은 항상 [0]배열을 제외하고 배열을 짜는 경향이 있는데, sort를 해줄때 begin()으로

sort를 시작해서 처음의 0도 같이 정렬이 되기때문에 0에 의해 사라지는 하나의 숫자가 있었기 때문이다.

begin()+1,end()로 정렬을 해주었다. 빈 공간을 두는것에 항상 조심을 해야할거 같다.

항상 테스트케이스는 전부 맞아도 틀리는 경우는, 하나의 배열 원소에 대해서 틀리는 경우가 많은거 같다.

 

문제

크기가 3×3인 배열 A가 있다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 커질 수 있다. R 연산이 적용된 경우에는 행의 크기가 가장 큰 행을 기준으로 모든 행의 크기가 커지고, C 연산이 적용된 경우에는 열의 크기가 가장 큰 열을 기준으로 모든 열의 크기가 커진다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 이 값이 100을 넘어가는 경우에는 -1을 출력한다.

 

 

#include <iostream>
#include<vector>
#include <algorithm>
using namespace std;
 
struct arr {
    int idx;
    int cnt;
    arr() {};
    arr(int idx, int cnt) :idx(idx), cnt(cnt) {};
};
 
int r, c, k, answer = 0;
int len_r = 3, len_c = 3, r_max = 0, c_max = 0;
int A[101][101] = { 0 }; //1~100
vector<arr> a(101);
 
bool cmp(arr a1, arr a2) {
    if (a1.cnt == a2.cnt) { //갯수가 같으면 오름차순
        if (a1.idx < a2.idx) return true;
        else return false;
    }
    if (a1.cnt < a2.cnt) return true; //갯수로 오름차순
    else return false;
}
 
void go1(int idx) {
    //A[idx][~]
    for (int i = 1; i < 101; i++) a[i]=arr(i, 0);
    for (int i = 1; i < 101 ; i++) {
        a[A[idx][i]].cnt++;
        A[idx][i] = 0;//다음을 위한 초기화
    }
    sort(a.begin()+1, a.end(),cmp); //a[0]이 없기때문에 .. 실수하기 딱좋네
    int cnt2 = 1;
    for (int i = 1; i < 101; i++) {
        if (cnt2 == 101) break;
        if (a[i].cnt != 0) {//A에 잘 대입
            A[idx][cnt2] = a[i].idx;
            A[idx][cnt2 + 1] = a[i].cnt;
            cnt2 += 2;
        }
    }
    if (c_max <= cnt2-1) c_max = cnt2-1; //최대 길이구하기
}
 
void go2(int idx) {
    //A[~][idx]
    for (int i = 1; i < 101; i++) a[i]=arr(i, 0);
    for (int i = 1; i < 101; i++) {
        a[A[i][idx]].cnt++;
        A[i][idx] = 0;//다음을 위한 초기화
    }
    sort(a.begin()+1, a.end(), cmp);
    int cnt2 = 1;
    for (int i = 1; i < 101; i++) {
        if (cnt2 == 101) break;
        if (a[i].cnt != 0) {
            A[cnt2][idx] = a[i].idx;
            A[cnt2+1][idx] = a[i].cnt;
            cnt2 += 2;
        }
    }
    if (r_max <= cnt2-1) r_max = cnt2-1;
}
 
int main()
{
    cin >> r >> c >> k;
    for (int i = 1; i <= 3; i++) for (int j = 1; j <= 3; j++) cin >> A[i][j];
 
    while (answer <= 100) {
        if (A[r][c] == k) break;
        //R>=C ,  R<C 의 경우를 나눠서 함수를 실행한다.
        if (len_r >= len_c) {
            c_max = 0;
            for (int i = 1; i <= len_r; i++) go1(i);
            len_c = c_max;
        }
        else {
            r_max = 0;
            for (int i = 1; i <= len_c; i++) go2(i);
            len_r = r_max;
        }
        answer++;
    }
 
    if (answer == 101) printf("-1");
    else printf("%d\n", answer);
    return 0;
}