17140. 이차원 배열과 연산 GOLD IV (C++)

문제

크기가 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 <algorithm>
#include <string.h>
#include <vector>
 
using namespace std;
 
int R,C,K, cnt[101], r_size, c_size,tr,tc;
vector<vector<int> > V (101);
vector<vector<int> > temp(101);
 
bool cmp(pair<int, int> p1, pair<int, int> p2)
{
    if (p1.first != p2.first)
        return p1.first > p2.first;
    else
    {
        return p1.second > p2.second;
    }
}
 
vector<pair<int, int> > pq;
 
void R_calc(int row)
{
    pq.clear();
    memset(cnt, 0, sizeof(cnt));
 
    for(int i=0;i<V[row].size();i++)
    {
        if(V[row][i] == 0) continue;
        cnt[V[row][i]]++;
    }
        
    for(int i=1;i<=100;i++)
    {
        if(cnt[i] == 0) continue;
        pq.push_back(make_pair(cnt[i],i));
    }
    sort(pq.begin(), pq.end(), cmp);
 
    V[row].clear();
    for(int i=0;i<pq.size();i++)
    {
        V[row].insert(V[row].begin(), pq[i].first);
        V[row].insert(V[row].begin(), pq[i].second);
        if(V[row].size() == 100) break;
    }
    if (V[row].size() > c_size) c_size = V[row].size();
}
 
void C_calc(int col)
{
    pq.clear();
    memset(cnt, 0, sizeof(cnt));
 
    for(int i=0;i<temp[col].size();i++)
    {
        if(temp[col][i] == 0) continue;
        cnt[temp[col][i]]++;
    }
 
    for(int i=1;i<=100;i++)
    {
        if(cnt[i] == 0) continue;
        pq.push_back(make_pair(cnt[i],i));
    }
    sort(pq.begin(), pq.end(), cmp);
 
    temp[col].clear();
    for(int i=0;i<pq.size();i++)
    {
        temp[col].insert(temp[col].begin(), pq[i].first);
        temp[col].insert(temp[col].begin(), pq[i].second);
        if(temp[col].size()==100) break;
    }
 
    if (temp[col].size() > r_size) r_size = temp[col].size();
    
}
 
 
void copy()
{
    for(int i=0;i<c_size;i++)
    {
        temp[i].clear();
        for(int j=0;j<r_size;j++)
            temp[i].push_back(0);
    }
        
    for(int i=0;i<c_size;i++)
    {
        for(int j=0;j<r_size;j++)
        {
            temp[i][j] = V[j][i];
        }
 
    }
        
}
 
void paste()
{
    for(int i=0;i<r_size;i++)
    {
        V[i].clear();
        for(int j=0;j<c_size;j++)
        {
            V[i].push_back(0);
        }
    }
 
    for(int i=0;i<temp.size();i++)
    {
        if(temp[i].size() == 0) return;
        for(int j=0;j<temp[i].size();j++)
            V[j][i] = temp[i][j];
    }
}
 
int solve()
{
    for(int ans = 0;ans<101;ans++)
    {
        if (V[R-1][C-1] == K) return ans;
        tr = r_size, tc = c_size;
        if (r_size >= c_size)
        {
            for(int row=0;row<tr;row++)
                R_calc(row);
 
            for(int row = 0;row<tr;row++)
                if(V[row].size() < c_size)
                {
                    for(int idx = V[row].size();idx<c_size;idx++)
                        V[row].push_back(0);
                }
 
        }
        else
        {
            copy();
            for(int col=0;col<tc;col++)
                C_calc(col);
            
            for(int col=0;col<tc;col++)
                if(temp[col].size() < r_size)
                    for(int idx = temp[col].size();idx<r_size;idx++)
                        temp[col].push_back(0);
            paste();
        }
        int rcnt = 0, ccnt = 0;
        r_size = 0, c_size = 0;
        for(int i=0;i<V.size();i++)
        {
            if(V[i].size() == 0) break;
            rcnt++;
            ccnt = 0;
            for(int j=0;j<V[i].size();j++)
            {
                if(V[i][j] != 0) ccnt ++;
            }
            if (ccnt > c_size) c_size = ccnt;
        }
        r_size = rcnt;
    }
 
    return -1;
 
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>R>>C>>K;
 
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            int in;
            cin>>in;
            V[i].push_back(in);
        }
    }
    for(int i=0;i<R;i++)
        for(int j=0;j<C;j++)
            V[i].push_back(0);
    r_size = 3, c_size = 3;
    cout<<solve()<<'\n';
    
    return 0;
}

코드 더럽게 길다 ㅠㅠ

예외 조건이 더럽게 많은데 처음 인풋이 

4 4 1

1 2 3

1 1 1

1 2 1 

2 3 4 

 

이렇게 3*3 벡터만 인풋을 받았지만 찾는 곳은 4 혹 그 이상일수 있기 때문에 solve() 함수 들어가기 전에 벡터의 크기를 충분히 크게 해줘야 한다. 

 

cmp 함수는 횟수 오름차순, 숫자 오름차순으로 정렬하는 함수다.

 

1. R이 큰 경우

  - [1,2,3]인 경우 1이 1개 2가 1개 3이 1개 이므로 [1, 1, 2, 1, 3, 1]이 된다

 

2. C가 큰 경우

 - 나는 temp 벡터를 사용했는데 clear, push_back등의 함수를 쓰려면 원래 벡터 V를 행과 열을 바꾼 temp 벡터로 만든다. 그리고 R행렬이 했던 것과 똑같이 연산을 수행하면 된다.

그리고 연산을 끝낸 후에 temp 행렬을 뒤집어 원래 모습으로 만들어 준다.