백준 17140. 이차원 배열과 연산 (구현)

https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

문제 요약:

1) 한 배열에 대해 정렬을 수행한다.

배열을 정렬하려면, 각각의 수가 몇번 나왔는지 세고, 수의 등장횟수가 커지는 순서, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 

순서는 수가 먼저이다. 

ex) [3, 1, 1] 1이 2번, 3이 1번 나옴 따라서 [3, 1, 1, 2]
ex) 위 배열을 다시 정렬하면 [2, 1, 3, 1, 1, 2]

 

2) 정렬을 할 배열은 행기준일수도 있고, 열기준일 수도 있다.

행의 개수 >= 열의 개수이면, 행에 대해서 정렬을 수행 (r연산)

행의 개수 < 열의 개수이면, 열에 대해서 정렬을 수행 (c연산)

 

3) 배열[r][c] 에 들어있는 값이 k가 되기 위한 연산의 최소 시간

 

1. 구현 포인트

1) 해당 행, 혹은 열에 수가 각각 몇개씩 들어있는지 구현: 키가 수, 값이 수의 개수인 이용

2) map을 벡터를 이용하여 정렬. (수의 개수가 커지는 순서로 정렬하고 그러한 것이 여러가지라면 수가 커지는 순으로 정렬)

3) 정렬된 벡터를 이용해서 2차원 배열을 업데이트함.

 

2. 삽질 포인트

1) 1.1을 구현할 때, 0은 개수를 세지 않기 때문에 해당 위치의 숫자가 0인 경우, 무시한다. 

2) 1.3을 구현할 때, 

 

 

사진의 3 3 3 -> 3 3 처럼 배열의 사이즈가 줄어드는 경우가 있다. 

이 때문에, 정렬된 벡터를 이용해 2차원 배열을 업데이트 했다면, 이 후에 값을 0으로 설정해주어야 한다. 

 

3. 코드

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int arr[202][202];
int r,c,k;
int ans;
int cur_r, cur_c; //현재 r, c개수

bool cmp(pair<int, int> a, pair<int, int> b)
{
    if(a.second == b.second) return a.first < b.first;
    else return a.second < b.second;
}
int main()
{           
    cin >> r >> c >> k;
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)
        {
            cin >> arr[i][j];
        }
    }
    r--;
    c--;
    
    cur_r = 3; //행 개수
    cur_c = 3; //열 개수
    
    
    
    int val;
    int num;
    while(true)
    {
        if(arr[r][c] == k) break;
        if(ans == 100)
        {
            cout << -1;
            return 0;
        }
        ans++;

        if(cur_r >= cur_c)
        {
            int mc = 0;
            for(int i = 0; i < cur_r; i++)
            {
                map<int, int> _map; //키가 수, 값이 수의 개수
                for(int j = 0; j < cur_c; j++)
                {
                    val = arr[i][j];
                    if(val == 0) continue;
                    _map[val] = _map[val] + 1;
                }
                
               
                //수의 개수가 커지는 순서로 정렬, 같다면 수가 커지게 정렬
                vector<pair<int, int>> sortmap(_map.begin(), _map.end());
                sort(sortmap.begin(), sortmap.end(), cmp);

        
                for(int j = 0; j < static_cast<int>(sortmap.size()); j++)
                {
                    arr[i][j*2] = sortmap[j].first;
                    arr[i][j*2+1] = sortmap[j].second;
                }
                int cnt = static_cast<int>(sortmap.size()) * 2;
                for(int j = cnt; j < cur_c; j++)
                    arr[i][j] = 0;
                
                mc = max(mc, static_cast<int>(sortmap.size()));
            }
            cur_c = mc * 2;
            
        }
        else
        {
            int mr = 0;
            for(int j = 0; j < cur_c; j++)
            {
                map<int, int> _map; //키가 수, 값이 수의 개수
                for(int i = 0; i < cur_r; i++)
                {
                    val = arr[i][j];
                    if(val == 0) continue;
                    _map[val] = _map[val] + 1;
                }
                //수의 개수가 커지는 순서로 정렬, 같다면 수가 커지게 정렬
                vector<pair<int, int>> sortmap(_map.begin(), _map.end());
                sort(sortmap.begin(), sortmap.end(), cmp);
                
                for(int i = 0; i < static_cast<int>(sortmap.size()); i++)
                {
                    arr[i*2][j] = sortmap[i].first;
                    arr[i*2+1][j] = sortmap[i].second;
                }
                int cnt = static_cast<int>(sortmap.size()) * 2;
                for(int i = cnt; i < cur_r; i++)
                    arr[i][j] = 0;
                mr = max(mr, static_cast<int>(sortmap.size()));
            }
            cur_r = mr * 2;   
        }  
    }
    cout << ans;
}