[백준 17140] 이차원 배열과 연산

문제 바로가기

17140번: 이차원 배열과 연산

 

시뮬레이션 문제이다

sort함수에서 compare 함수로 custom하게 사용할 수 있다는 것을 알게됐다

R_calculate이랑 C_calculate이랑 로직은 똑같은데 수행하는 게 열 기준/행 기준만 다른데,,

두개를 합치면 더 간단한 코드가 될 수 있을 것 같은데

모르겠당 ㅎ

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string.h>

using namespace std;

int arr[201][201];
int ncount[201];

int r, c, k;
int cN, cM;
int time;

bool compare(pair<int, int> a, pair<int, int> b)
{
    if (a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}
pair<int,int> R_calculate()
{
    int max_arri = 0;
    for (int i = 1; i <= cN; i++)
    {
        int maxx = 0;
        memset(ncount, 0, sizeof(ncount));
        vector<pair<int, int>> number;
        for (int j = 1; j <= cM; j++)
        {
            ncount[arr[i][j]]++;
            maxx = max(maxx, arr[i][j]);
            arr[i][j] = 0;
        }

        for (int j = 1; j <= maxx; j++)
        {
            number.push_back({ j, ncount[j] });
        }
        sort(number.begin(), number.end(), compare);

        int arri = 1;

        for (pair<int, int> tmp : number)
        {
            if (tmp.second)
            {
                arr[i][arri++] = tmp.first;
                arr[i][arri++] = tmp.second;
            }
        }
        max_arri = max(max_arri, arri);
    }

    return { cN, max_arri };
}

pair<int,int> C_calculate()
{
    int max_arri = 0;
    for (int i = 1; i <= cM; i++)
    {
        int maxx = 0;
        memset(ncount, 0, sizeof(ncount));
        vector<pair<int, int>> number;
        for (int j = 1; j <= cN; j++)
        {
            ncount[arr[j][i]]++;
            maxx = max(maxx, arr[j][i]);
            arr[j][i] = 0;
        }

        for (int j = 1; j <= maxx; j++)
        {
            number.push_back({ j, ncount[j] });
        }
        sort(number.begin(), number.end(), compare);

        int arri = 1;

        for (pair<int, int> tmp : number)
        {
            if (tmp.second)
            {
                arr[arri++][i] = tmp.first;
                arr[arri++][i] = tmp.second;
            }            
        }
        max_arri = max(max_arri, arri);
    }

    return { max_arri, cM };
}
int main()
{
    cin >> r >> c >> k;
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++)
        {
            cin >> arr[i][j];
        }
    }
    cN = 3;
    cM = 3;

    while (arr[r][c] != k)
    {
        time++;
        if (time > 100)
        {
            time = -1;
            break;
        }
        if (cM <= cN)
        {
            pair<int,int> newSize = R_calculate();
            cN = newSize.first;
            cM = newSize.second;
        }

        else {
            pair<int, int> newSize = C_calculate();
            cN = newSize.first;
            cM = newSize.second;
        }

    }

    cout << time << endl;

    return 0;
}