이차원 배열과 연산_17140

문제 출처 : 이차원배열과연산_17140

파라미터 정리

초기 배열 크기 3x3, A[3][3]
1초마다 R혹은 C연산이 적용됨
R 모든 행에 대해 정렬 (행>=열)
C 모든 열에 대해 정렬 (행< 열)
(숫자, 해당 수가 등장한 횟수) 순서로 정렬
등장한 횟수가 적은 것이 먼저 등장
등장한 횟수가 같을 때에는 숫자가 작은 것이 먼저 등장
연산 후 행/열의 크기가 달라질 수 있음
R : 가장 큰 행을 기준으로 모든 행의 크기가 변함
C : 가장 큰 열을 기준으로 모든 열의 크기가 변함
빈칸이 발생하면 0으로 채우고 다음 연산 때 0의 값은 무시됨
행/열의 크기가 100을 넘어가는 경우에는 나머지를 버림
input : r,c,k (r 원하는 행, c 원하는 열, k 원하는 값) (1 ~ 100)
output : A[r][c] == k가 되기 위한 최소 시간 (100이 넘어가면 -1 출력)

간략한 과정

input_1 r,c,k 입력받기
input_2 초기 배열 A[r][c] 입력받기
A[r][c] 입력 받은 부분을 제외하고는 0으로 초기화 되어있음
A[r][c]의 값이 k와 같은지 확인하기
같으면 시간 CNT 값 반환, 다르면 행렬 연산 실행하고 CNT+1
(이 때 CNT가 100이상이면 return -1)
행/렬 크기 비교하고 R 혹은 C 연산 실행하기
R/C 연산 구현{
개수가 적은 수부터 정렬하기 위해 자료형 pair {개수, 숫자} 사용하기
새로운 벡터에 행/열의 값을 넣고 sort, iter를 이용해서 pair 변수를 채움
pair를 sort해서 개수가 적은 것 먼저 배치
만약 갯수가 같을 때에는 숫자가 작은 것 먼저 배치
결과값을 A배열에 적용시키기
이때 결과값이 100이상이면 break 이용해서 나머지 버리기
숫자값이 가장 큰 것을 cnt_r/c에 넣기 -> 다음 연산 때 cnt_r/c까지 계산하면 됨
}
output CNT를 출력한다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int r, c, k;
int Map[100][100] = {0};
int r_size = 3, c_size = 3;

int solve(int cnt){
    if(cnt > 100) return -1;
    if(Map[r-1][c-1] == k) return cnt;
    
    if(r_size >= c_size){//R 연산
        //각 행에 대해서 실시
        for(int i = 0; i < r_size; i++){
            vector<int> r_list;
            vector<pair<int,int>> n_Row;
            //i번째 row의  첫번째 col부터 마지막 col까지 벡터에 옮김
            for(int j = 0; j < c_size; j++){
                if(Map[i][j] == 0) continue;
                r_list.push_back(Map[i][j]);
                Map[i][j] = 0;
            }
            //i번째 row의 값 오름차순으로 정렬
            //{개수, 숫자}로 만들어서 새로운 벡터에 옮김
            sort(r_list.begin(), r_list.end());
            int num = 0;
            for(int k = 0; k < r_list.size(); k++){
                num++;
                if(r_list[k] != r_list[k+1] || k == r_list.size()-1){
                    n_Row.push_back({num, r_list[k]});
                    num = 0;
                }
            }
            //개수가 적은 순으로 정렬
            //위에 sort로 인해서 개수가 같을 때 숫자 적은 게 먼저 위치함
            sort(n_Row.begin(), n_Row.end());
            num = 0;
            int n_size = n_Row.size();
            for(int t = 0; t < n_size; t++){
                if(num >= 99) break;
                Map[i][num++] = n_Row[t].second;
                Map[i][num++] = n_Row[t].first;
            }     
             c_size = max(c_size, n_size*2);
        }
    }else{//C 연산
        for(int j = 0; j < c_size; j++){
            vector<int> c_list;
            vector<pair<int,int>> n_Col;
            for(int i = 0; i < r_size; i++){
                if(Map[i][j] == 0) continue;
                c_list.push_back(Map[i][j]);
                Map[i][j] = 0;
            }
            sort(c_list.begin(), c_list.end());
            int num = 0;
            for(int k = 0; k < c_list.size(); k++){
                num++;
                if(c_list[k] != c_list[k+1] || k == c_list.size()-1){
                    n_Col.push_back({num, c_list[k]});
                    num = 0;
                }
            }
            sort(n_Col.begin(), n_Col.end());
            num = 0;
            int n_size = n_Col.size();
            for(int t = 0; t < n_size; t++){
                if(num >= 99) break;
                Map[num++][j] = n_Col[t].second;
                Map[num++][j] = n_Col[t].first;
            }     
             r_size = max(r_size, n_size*2);
        }
    }

    return solve(cnt+1);
}

int main()
{
    cin >> r >> c >> k;
    for(int i = 0; i < 3; i++)
        for(int j = 0 ; j < 3; j++)
            cin >> Map[i][j];
    cout << solve(0) << endl;

    return 0;
}

시행착오

pair<int,int>>를 사용하지 않고, struct로 정의한 후 구현하면 9%대에서 테스트 통과하지 못했음. sort과정에서 문제가 발생하는 걸로 보임.