BOJ : 17140 이차원 배열과 연산

---

[BOJ 17140(G4) 리뷰]

풀면서 이게 시간내에 통과될까? 라는 생각을 몇번했는지 모르겠다. 구현방법은 바로 떠올랐는데 어떻게 하면 효율적으로 처리할수 있을지가 문제였다. 아무리 고민해도 더 좋은 코드가 떠오르지 않아 그냥 처음 생각한 방법대로 했는데 TC가 약해서인지 통과되었다.

 

이 문제는 R연산과 C연산을 통해 이루어진다.

R연산을 하면 각 행마다의 숫자와 등장횟수를 오름차순으로 변경해주면 된다.

예를들어 1 1 2 라는 행이 있으면 1이 2번등장 2가 1번등장했으므로 -> 2 1 1 2 로 변경된다.

1 2 1

2 1 3

3 3 3

라는 행렬이 있으면

1 2 2 1 0 0

1 1 2 1 3 1

3 3 0 0 0 0 으로 변경된다.

가장 큰 행을 기준으로 나머지값은 0으로 채워주는 작업도 필요하다.

C연산은 행이 아닌 열에 동일한 작업을 수행해주면 된다.

 

나는 Roper와 Coper함수를 만들어 위 연산을 수행하게 했다. 이때 효율적인 방법을 고민했는데 떠올리지 못했고 그냥 처음에 생각했던대로 반복문을 돌며 cnt배열에 등장하는 횟수를 기록했다.

그 후에 cnt배열에 기록된 등장횟수를 벡터에 저장한다. 이때 주의해야할것은 <등장횟수,숫자> 로 저장해야만 오름차순으로 정렬했을때 등장횟수가 적은것부터 출력이 가능하다.

이후에는 벡터를 돌며 해당 행 또는 열의 값을 바꿔주면 된다.

함수화를 조금더 세분화하면 코드를 더 깔끔하게 짤 수 있으나 귀찮아서 내버려뒀다.

 

(다음에는 연산을 하나만 구현해놓고 행렬을 회전시켜서 처리하는 테크닉도 도전해봐야겠다.)

---

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
 
int map[101][101];
int cnt[101] = { 0, };
int r, c, k;
int maxR = 3;
int maxC = 3;
vector <pair<int, int>> vc;
 
int Roper()
{
    int maxret = 0;
    for (int i = 1; i <= maxR; i++)
    {
        vc.clear();
        fill(cnt, cnt + 101, 0);
        for (int j = 1; j <= maxC; j++)
        {
            if (map[i][j] == 0) continue;
            cnt[map[i][j]]++;
        }
        for (int h = 1; h <= 100; h++)
        {
            if (!cnt[h]) continue;
            int len = vc.size();
            int check = true;
            for (int k = 0; k < len; k++)
            {
                if (vc[k].second == h)
                {
                    vc[k].first++;
                    check = false;
                    break;
                }
            }
            if(check)
                vc.push_back({ cnt[h],h });
        }
        sort(vc.begin(), vc.end());
        fill(map[i], map[i] + maxC +1 , 0);
        int len = vc.size();
        int idx = 1;
        for (int v = 0; v < len; v++)
        {
            map[i][idx++] = vc[v].second;
            map[i][idx++] = vc[v].first;
        }
        maxret = max(maxret, len * 2);
    }
 
    return maxret;
}
 
int Coper()
{
    int maxret = 0;
    for (int i = 1; i <= maxC; i++)
    {
        vc.clear();
        fill(cnt, cnt + 101, 0);
        for (int j = 1; j <= maxR; j++)
        {
            if (map[j][i] == 0) continue;
            cnt[map[j][i]]++;
        }
        for (int h = 1; h <= 100; h++)
        {
            if (!cnt[h]) continue;
            int len = vc.size();
            int check = true;
            for (int k = 0; k < len; k++)
            {
                if (vc[k].second == h)
                {
                    vc[k].first++;
                    check = false;
                    break;
                }
            }
            if (check)
                vc.push_back({ cnt[h],h });
        }
        sort(vc.begin(), vc.end());
        for (int h = 1; h <= maxR; h++)
        {
                map[h][i] = 0;
        }
        int len = vc.size();
        int idx = 1;
        for (int v = 0; v < len; v++)
        {
            map[idx++][i] = vc[v].second;
            map[idx++][i] = vc[v].first;
        }
        maxret = max(maxret, len * 2);
    }
 
    return maxret;
}
 
int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    
    cin >> r >> c >> k;
    for (int i = 1; i <= maxR; i++)
    {
        for (int j = 1; j <= maxC; j++)
            cin >> map[i][j];
    }
    
    int cnt = 0;
    while (1)
    {
        if (map[r][c] == k) break;
        if (cnt > 100)
        {
            cout << -1;
            exit(0);
        }
        if (maxR >= maxC)
        {
            maxC = Roper();
        }
        else
        {
            maxR = Coper();
        }
        cnt++;
    }
 
    cout << cnt;
    
}