[C++] 백준 17140번: 이차원 배열과 연산

🔗 문제

17140번: 이차원 배열과 연산

17140번: 이차원 배열과 연산

크기가 3×3 (초기 배열 크기 3) 인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

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

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

 

예를 들어, [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이 채워진다. (map에 덮어쓰는게 아니라 새로운 배열에 결과를 넣고 덮어써야하는 이유 222 ) 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

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

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

 

100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

 

🖍 풀이

 

 3시간 동안 풀었는데 풀이 쓰다보니까 왜 그렇게 답답하게 헤맸는지 이해가 안 된다. 

 

문제를 꼼꼼히 읽어보자. 밑줄 친 부분을 읽어보면 일단 크게 흐름은 아래처럼 정리할 수 있다.

int solve()
{
	while(map[X][Y] != K)
	{
		if(R < C) Csort();
		else Rsort();
		if(++answer == 1000) return -1;
	}
	return answer;
}

 

R연산이나 C연산이나 비슷하니까 R 연산을 하는 방법으로 풀이를 써보겠습니다..

 

 

✔️ 1.  행에 저장된 숫자를 저장한다. 

이 때, 수를 정렬할 때 0은 무시하며 최대 저장된 수의 크기가 100이라 num[숫자]에 등장횟수 저장한다.

for(int i=0; i<R; ++i)
{
        std::vector<int> num(MAX, 0);
        for(int j=0; j<C; ++j)
        {
            if(map[i][j] == 0) continue;
            ++num[map[i][j]];
        }
       

 

 

✔️ 2. 수와 등장횟수를 조건에 맞게 정렬한다.

과정 1에서 저장한 값을 이용해 일단 수와 등장횟수를 저장해준다.

std::vector<pii> tmp;
for(int k=1; k<MAX; ++k)
{
    if(num[k] == 0) continue;
    tmp.push_back({k, num[k]});
}

 

수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬해야 한다.

1. 등장 횟수 오름차순
2. 수 오름차순

이 조건을 만족하는 정렬 함수를 커스텀해주면 됩니다. (이게 중요)

typedef std::pair<int, int> pii;

struct cmp
{
    // first, second = 숫자 , 등장횟수

    bool operator()(const pii& a, const pii& b)
    {
        if(a.second == b.second) // 등장횟수가 같다면 숫자 오름차순으로!
            return a.first < b.first;
        
        return a.second <= b.second; // 등장 횟수 오름차순
    }
};

std::sort(tmp.begin(), tmp.end(), cmp());

 

✔️ 3. 새로운 배열에 정렬된 값을 저장한다. 

R 연산을 하면서 C (열 길이)가 바뀌기 때문에 더 큰 값으로 갱신해주어야 한다.

길이가 바뀌면서 0으로 덮어쓰는 과정을 할거면 덮어써도 되는데... 굳이!!!! ??? 라서  새로운 배열 out에 정렬된 값을 저장한다.  

C = (C > tmp.size()*2 ? C : tmp.size()*2);
int idx = 0;
for(int k=0; k<tmp.size(); ++k)
{
    out[i][idx++] = tmp[k].first;
    out[i][idx++] = tmp[k].second;
}

그리고 나서 새로운 배열과 기존 배열을 swap해주고 반복하면 끝.

 

💾  소스

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <memory.h>

const int MAX  = 100 + 1;

typedef std::pair<int, int> pii;

int X, Y, K;
int R = 3, C = 3;

int map[MAX][MAX] = {0, };

bool isValid(const int x, const int y)
{
    if(x<0 || y<0 || x>=MAX|| y>=MAX)
        return false;
    return true;
}

void show(int (*map)[MAX])
{
    for(int i=0; i<R; ++i)
    {
        for(int j=0; j<C; ++j)
            std::cout << map[i][j] << ' ';
        std::cout << '\\n';
    }
}

struct cmp
{
    // first, second = 숫자 , 등장횟수
    // 1. 등장 오름차순
    // 2. 숫자 오름차순
    bool operator()(const pii& a, const pii& b)
    {
        if(a.second == b.second)
            return a.first < b.first;
        
        return a.second <= b.second;
    }
};

void Rsort(int (*out)[MAX])
{
    for(int i=0; i<R; ++i)
    {
        std::vector<int> num(MAX, 0);
        for(int j=0; j<C; ++j)
        {
            if(map[i][j] == 0) continue;
            ++num[map[i][j]];
        }
        
        std::vector<pii> tmp;
        for(int k=1; k<MAX; ++k)
        {
            if(num[k] == 0) continue;
            tmp.push_back({k, num[k]});
        }
        std::sort(tmp.begin(), tmp.end(), cmp());
        
        C = (C > tmp.size()*2 ? C : tmp.size()*2);
        int idx = 0;
        for(int k=0; k<tmp.size(); ++k)
        {
            out[i][idx++] = tmp[k].first;
            out[i][idx++] = tmp[k].second;
        }
    }
}

void Csort(int (*out)[MAX])
{
    for(int i=0; i<C; ++i)
    {
        std::vector<int> num(MAX, 0);
        for(int k=0; k<R; ++k)
        {
            if(map[k][i] == 0) continue;
            ++num[map[k][i]];
        }
        
        std::vector<pii> tmp;
        for(int k=1; k<MAX; ++k)
        {
            if(num[k] == 0) continue;
            tmp.push_back({k, num[k]});
        }
        std::sort(tmp.begin(), tmp.end(), cmp());
        
        int idx = 0;
        R = (R > tmp.size()*2 ? R : tmp.size()*2);
        for(int k=0; k<tmp.size(); ++k)
        {
            out[idx++][i] = tmp[k].first;
            out[idx++][i] = tmp[k].second;
        }
    }
}

int solve()
{
    int answer = 0;
    
    while(map[X-1][Y-1] != K)
    {
        //printf("%d => [%d][%d] = %d\\n", answer, X-1, Y-1, map[X-1][Y-1]);
        //show(map);
        int arr[MAX][MAX] = {0, };

        if(R < C)
            Csort(arr);
        else
            Rsort(arr);
                
        memset(map, 0, sizeof(map));
        for(int i=0; i<R; ++i)
            for(int j=0; j<C; ++j)
                map[i][j] = arr[i][j];
        
        if(++answer == 1000)
                  return -1;
    }
    return answer;
}

int main()
{
    std::cin >> X >> Y >> K;
    
    for(int i=0; i<3; ++i)
        for(int j=0; j<3; ++j)
            std::cin >> map[i][j];

    std::cout << solve();
    
    return 0;
}