[BOJ 17140] 이차원 배열과 연산(C++)

이차원 배열과 연산 Gold 4

문제

전체 문제 보기

17140번: 이차원 배열과 연산

접근법

문제서 제시된 R연산과 C연산을 구현하여 시뮬레이션하여 풀 수 있는 문제입니다. R연산과 C연산은 행과 열이 역전된 것 외에 동일하기 때문에 R연산에 대해서 먼저 설명해보도록 하겠습니다.

R연산

R연산을 하기 위해서는 각 행마다 존재하는 수의 등장 횟수를 세어야 합니다. 이러기 위해서 2가지를 생각해봐야합니다.

• 한 행에 수가 몇 개인지 어떻게 확인할 것인가
• 수의 등장 횟수를 어디에 저장할 것인가?

먼저 한 행에 존재하는 수의 개수는 각 행마다 다릅니다. 따라서 각 행마다 수가 몇 개씩 있는지 기록해둬야 합니다. 문제에서는 최대 100 * 100 행렬이 사용되기 때문에 101 * 101 행렬을 선언한 뒤 각 행의 첫 번째수 와 각 열의 첫 번째 수는 해당 행과 열에 몇개의 수가 저장되어있는지 기록하는 용도로 사용합니다. 문제에서 주어진 3번 째 예시를 한번의 연산을 진행할 때마다 출력하면 다음과 같이 출력됩니다. 아래의 출력에서 각 행과 열의 첫번째 수는 해당 행과 열에 수가 몇 개 있는지를 나타냅니다.

1 2 1
2 1 3
3 3 3
row: 3 col: 6
0 3 3 2 2 2 2
4 2 1 1 2 0 0
6 1 1 2 1 3 1
2 3 3 0 0 0 0

row: 6 col: 6
0 6 4 4 4 2 2
6 1 3 1 1 3 1
6 1 1 1 1 1 1
4 2 1 2 2 0 0
4 1 2 1 1 0 0
1 3 0 0 0 0 0
1 1 0 0 0 0 0

다음으로 하나의 행에 등장하는 수의 개수는 hash map, map, 배열 등에 저장하는 방법이 있습니다. 각각의 장단점이 존재합니다. map은 공간 효율이 가장 좋습니다. 만약 5종류의 수가 있다면 map은 5칸만으로 해당 수들을 기록할 수 있습니다. 대신 수를 탐색하기 위해서 (logN)만큼의 시간이 필요합니다. hash map은 버킷의 크기가 넉넉하게 할당되다 보니 map보다 더 많은 공간이 요구됩니다. 대신 상수 시간 복잡도를 가집니다. 배열을 활할 경우 0~100까지 수를 담아야 하기 때문에 가장 많은 공간이 필요합니다. 하지만 한 번의 인덱싱으로 접근할 수 있기 때문에 가장 빠른 성능을 보입니다. 저는 이번 문제에서는 map을 활용하여 풀이를 진행하였습니다.

 

R 연산은 다음과 같이 구현하였습니다.

void OperatorR(Mat& mat, int& row, int& col)
{
    col = 0;
    for (int i = 1; i <= row; ++i)
    {
        std::map<int, int> map;
        for (int j = 1; j <= mat[i][0]; j++)
        {
            if (mat[i][j] == 0) continue;
            map[mat[i][j]]++;
            mat[i][j] = 0;
        }
        mat[i][0] = std::min((int)(map.size() * 2), 100);
        std::vector<std::pair<int, int>> vec;
        SortOneLine(map, vec);

        for (int j = 1; j <= mat[i][0]; j += 2)
        {
            mat[i][j] = vec[j / 2].first;
            mat[i][j + 1] = vec[j / 2].second;
        }
        col = std::max(col, mat[i][0]);
        for (int j = 1; j <= mat[i][0]; ++j)
        {
            mat[0][j] = i;
        }

    }
}

SortOneLine 함수에서는 아래와 같이 문제에서 요구한 순서대로 배열을 정렬하는 연산을 진행합니다. 문제에 요구한 바는 다음과 같습니다. 아래의 요구사항 람다로 표현하였으며, 이를 sort함수에 전달하여 정렬하였습니다.

• 등장 회수를 기준으로 오름차순 정렬
• 등장 횟수가 동일할 경우 해당 수를 기준으로 오름차순 정렬

void SortOneLine(std::map<int, int>& map, std::vector<std::pair<int, int>>& vec)
{
    vec.reserve(map.size());

    auto iter = map.begin();
    while (iter != map.end() && vec.size() < 50)
    {
        vec.push_back(*iter);
        iter++;
    }
    auto comp = [](const std::pair<int, int>& lhs, const std::pair<int, int>& rhs)
    {
        if (lhs.second < rhs.second) return true;
        else if (lhs.second == rhs.second && lhs.first < rhs.first) return true;
        return false;
    };
    std::sort(vec.begin(), vec.end(), comp);
}

전체 구현

C연산은 R과 행과 열을 반전시킨 것을 제외하면 모두 동일하기 때문에 별도의 설명은 생략합니다. 아래와 같이 문제를 해결할 수 있습니다.

#include <iostream>
#include <map>
#include <array>
#include <algorithm>
#include <vector>
#define endl '\n'

using Mat = std::array<std::array<int, 101>, 101>;
void PrintMat(const Mat& mat, int row, int col)
{
    std::cout << "row: " << row << " col: " << col << endl;
    for (int i = 0; i <= row; ++i)
    {
        for (int j = 0; j <= col; ++j)
        {
            std::cout << mat[i][j] << " ";
        }
        std::cout << endl;
    }
    std::cout << endl;
}
void SortOneLine(std::map<int, int>& map, std::vector<std::pair<int, int>>& vec)
{
    vec.reserve(map.size());

    auto iter = map.begin();
    while (iter != map.end() && vec.size() < 50)
    {
        vec.push_back(*iter);
        iter++;
    }
    auto comp = [](const std::pair<int, int>& lhs, const std::pair<int, int>& rhs)
    {
        if (lhs.second < rhs.second) return true;
        else if (lhs.second == rhs.second && lhs.first < rhs.first) return true;
        return false;
    };
    std::sort(vec.begin(), vec.end(), comp);
}
void OperatorC(Mat& mat, int& row, int& col)
{

    row = 0;
    for (int i = 1; i <= col; ++i)
    {
        std::map<int, int> map;
        for (int j = 1; j <= mat[0][i]; j++)
        {
            if (mat[j][i] == 0) continue;
            map[mat[j][i]]++;
            mat[j][i] = 0;
        }

        mat[0][i] = std::min((int)(map.size() * 2), 100);
        std::vector<std::pair<int, int>> vec;
        SortOneLine(map, vec);

        for (int j = 1; j <= mat[0][i]; j += 2)
        {
            mat[j][i] = vec[j / 2].first;
            mat[j+1][i] = vec[j / 2].second;
        }

        row = std::max(row, mat[0][i]);

        for (int j = 1; j <= mat[0][i]; ++j)
        {
            mat[j][0] = i;
        }
    }

}
void OperatorR(Mat& mat, int& row, int& col)
{
    col = 0;
    for (int i = 1; i <= row; ++i)
    {
        std::map<int, int> map;
        for (int j = 1; j <= mat[i][0]; j++)
        {
            if (mat[i][j] == 0) continue;
            map[mat[i][j]]++;
            mat[i][j] = 0;
        }
        mat[i][0] = std::min((int)(map.size() * 2), 100);
        std::vector<std::pair<int, int>> vec;
        SortOneLine(map, vec);

        for (int j = 1; j <= mat[i][0]; j += 2)
        {
            mat[i][j] = vec[j / 2].first;
            mat[i][j + 1] = vec[j / 2].second;
        }
        col = std::max(col, mat[i][0]);
        for (int j = 1; j <= mat[i][0]; ++j)
        {
            mat[0][j] = i;
        }

    }
}

void MatSort(Mat& mat, int& row, int &col)
{
    if (row >= col)
        OperatorR(mat, row, col);
    else
        OperatorC(mat, row, col);
}

int main()
{    
    //입출력 성능향상을 위한 설정
    std::ios_base::sync_with_stdio(false);
    std::cout.tie(NULL);
    std::cin.tie(NULL);

    Mat mat{};
    int r, c, k; // (1 ≤ r, c, k ≤ 100)
    std::cin >> r >> c >> k;
    for (int i = 1; i < 4; ++i)
    {
        for (int j = 1; j < 4; ++j)
        {
            std::cin >> mat[i][j];
        }
    }
    for (int i = 1; i <= 100; ++i)
    {
        mat[0][i] = 3;
        mat[i][0] = 3;
    }
    int row, col;
    row = col = 3;
    int answer{};
    while (mat[r][c] != k)
    {
        answer++;
        if (answer > 101)
        {
            answer = -1;
            break;
        }
        MatSort(mat, row, col);
    }

    std::cout << answer << endl;
    return 0;
}

결과