[ 백준 17140 ] 이차원 배열과 연산 (C++) - 구현

---

🔗 문제 링크

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

---

💡 문제 풀이 및 해석

1. 33배열이 주어지고, 최대로 늘어날 수 있는 크기는 100이다. 따라서 미리 100100 크기의 배열로 만들어준다. 단, r,c가 1이상이므로 인덱스도 1~100까지 즉 101칸을 만든다.
2. R과 C연산을 만들어야 하는데, 간단하다. 칸이 100개 이하이므로 상식적으로 숫자가 1이 100개가 들어가도 100이니 배열의 크기도 100으로 고정해두면 된다. 단, 인덱스는 숫자를 판단해야 하므로 1~100으로 정한다.
3. 이제 연산에서 각 번호를 인덱스에 카운팅하고, pair<카운팅된 숫자, 카운팅된 횟수> 로 vector에 넣어준다. 이 다음에 조건에 맞게 compare 함수를 만들고, 조건에 맞게 정렬해준다.
4. R과 C 연산을 100번 이하로 돌린다.(100번까지 돌려야한다.) 마지막 100번째 연산후에 완성될 수도 있으므로 101번까지 체크해야 한다. 왜? 어차피 101번 돌린 것은 if (arr[r][c] == k) return cnt;에 검사되지 않고, 99번 돌린것은 cnt == 100일 때, if (arr[r][c] == k) return cnt;에 검사되기 때문이다.

---

⭐️ 정답 코드 및 설명

#include<iostream>
#include<algorithm>
#include<vector>
#define MAX 101
#define endl "\n"

using namespace std;

int r, c, k, row = 3, col = 3;
int arr[MAX][MAX];
int numCount[MAX];

void input() {
    cin >> r >> c >> k;
    for (int y = 1; y <= 3; y++) {
        for (int x = 1; x <= 3; x++) {
            cin >> arr[y][x];
        }
    }
}

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;
}

void R() {
    for (int y = 1; y <= row; y++) {
        for (int i = 1; i <= 100; i++) numCount[i] = 0;
        for (int x = 1; x <= col; x++) numCount[arr[y][x]]++;

        vector<pair<int, int> > sum;
        for (int i = 1; i <= 100; i++) {
            if (numCount[i] == 0) continue;
            sum.push_back({i, numCount[i]});
        }
        sort(sum.begin(), sum.end(), compare);

        // vector<int> temp;
        // for (int i = 0; i < sum.size(); i++) {
        //     temp.push_back(sum[i].first);
        // }
        // for (int i = 0; i < sum.size(); i++) {
        //     temp.push_back(sum[i].second);
        // }
        for (int i = 1; i <= col; i++) arr[y][i] = 0;

        int index = 1;
        for (int i = 0; i < sum.size(); i++) {
            if (i == 50) break;
            arr[y][index++] = sum[i].first;
            arr[y][index++] = sum[i].second;
        }
        int a = sum.size() * 2;
        col = max(col, a);
    }
    if (col > 100) col = 100;
}

void C() {
    for (int x = 1; x <= col; x++) {
        for (int i = 1; i <= 100; i++) numCount[i] = 0;
        for (int y = 1; y <= row; y++) numCount[arr[y][x]]++;

        vector<pair<int, int> > sum;
        for (int i = 1; i <= 100; i++) {
            if (numCount[i] == 0) continue;
            sum.push_back({i, numCount[i]});
        }
        sort(sum.begin(), sum.end(), compare);

        for (int i = 1; i <= col; i++) arr[i][x] = 0;

        int index = 1;
        for (int i = 0; i < sum.size(); i++) {
            if (i == 50) break;
            arr[index++][x] = sum[i].first;
            arr[index++][x] = sum[i].second;
        }

        int a = sum.size() * 2;
        row = max(row, a);
    }
    if (row > 100) row = 100;
}

int sol() {
    int cnt = 0;
    while (cnt <= 100) {
        if (arr[r][c] == k) return cnt;

        if (row >= col) R();
        else C();

        cnt++;
    }
    return -1;
}


int main() {
    input();
    cout << sol();
    return 0;
}

---

🤔 문제 후기

주석처리한 부분처럼 처음에는 문제 조건을 카운팅된 수와 숫자를 분리하여 정렬하는 방식인줄 알았다. 즉, [3,1,1,2] -> [2,3,1,1,1,2]이런식으로 되는 것인줄 알고, 1시간 동안 오류를 찾지 못했다...

(오류가 없으니깐..)

 그래서 문제를 내려보다가 아래 힌트를보고 정렬하는 방식을 깨달은 뒤에는 바로 풀렸던 것 같다. 문제를 다시 한 번 꼼꼼히 읽고 문제를 이해하는 능력을 키워야겠다고 생각했다.