삼성 알고리즘 기출 문제 이차원 배열과 연산[백준-17140]

문제

출처

17140번: 이차원 배열과 연산

요약

• vector sort

#include <vector>
#include <algorithm>

class CountCell {
public:
    int value, count;

    void setCount(int count) {
        this->count = count;
    }

};

bool sortCC(const CountCell& c1, const CountCell& c2){
    if (c1.count == c2.count) {
        return c1.value < c2.value;
    }
    else {
        return c1.count < c2.count;
    }
}

vector<CountCell> cc;
vector<CountCell>::iterator iter;

sort(cc.begin(), cc.end(), sortCC);

풀이

1. 입력
2. solve
   1. 100번 돌았거나, 정답이면 끝.
   2. 행 개수 ≥ 열 개수이면 R연산
      1. vector<CountCell> cc초기화
         숫자가 몇 개 있는지 세기 위해서 저장.
      2. 한 행에서 모든 원소를 보면서 개수를 cc에 저장.
         cc 에 {숫자, 개수}형식으로으로 저장.
      3. cc에 저장된 원소들을 정렬.
         맴버 변수 count로 1순위 정렬
         맴버 변수 value로 2순위 정렬
      4. 해당 행에 최대 열 개수를 최신화.
   3. 행 개수 < 열 개수이면 C연산
      1. vector<CountCell> cc초기화
         숫자가 몇 개 있는지 세기 위해서 저장.
      2. 한 열에서 모든 원소를 보면서 개수를 cc에 저장.
         cc 에 {숫자, 개수}형식으로으로 저장.
      3. cc에 저장된 원소들을 정렬.
         맴버 변수 count로 1순위 정렬
         맴버 변수 value로 2순위 정렬
      4. 해당 행에 최대 행 개수를 최신화.
3. 결과 출력

소스코드

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <vector>

using namespace std;

int R, C, K;    // R=row, C=cell, K=count
int result = 0;
int maxR = 3, maxC = 3;    // max Row, max Cell
int a[1000][1000];

class CountCell {
public:
    int value, count;

    void setCount(int count) {
        this->count = count;
    }

};
vector<CountCell> cc;
vector<CountCell>::iterator iter;

bool sortCC(const CountCell& c1, const CountCell& c2){
    if (c1.count == c2.count) {
        return c1.value < c2.value;
    }
    else {
        return c1.count < c2.count;
    }
}

int solve() {

    while (true) {

        if (result == 10) {
            result = result;
        }
        if (a[R-1][C-1] == K) {
            return result;
        }
        if (result > 100) {
            return -1;
        }
        result++;
        if (maxR >= maxC) {    // R연산
            int newMax = 0;
            for (int r = 0; r < maxR; r++) {
                cc.clear();

                for (int c = 0; c < maxC; c++) {
                    int num = a[r][c];
                    if (num != 0) {
                        for (iter = cc.begin(); iter != cc.end(); iter++) {
                            int value = iter->value;
                            if (value == num) {
                                iter->setCount(iter->count + 1);
                                break;
                            }
                        }
                        if (iter == cc.end()) {
                            cc.push_back({ num, 1 });
                        }
                    }
                }
                sort(cc.begin(), cc.end(), sortCC);

                int cellNum = 0;
                for (iter = cc.begin(); iter != cc.end(); iter++) {
                    a[r][cellNum++] = iter->value;
                    a[r][cellNum++] = iter->count;
                }
                while (cellNum < maxC) {
                    a[r][cellNum++] = 0;
                }

                newMax = max(newMax, cellNum);
            }
            maxC = newMax;
        }
        else {    // C연산
            int newMax = 0;
            for (int c = 0; c < maxC; c++) {
                cc.clear();

                for (int r = 0; r < maxR; r++) {
                    int num = a[r][c];
                    if (num != 0) {
                        for (iter = cc.begin(); iter != cc.end(); iter++) {
                            int value = iter->value;
                            if (value == num) {
                                iter->setCount(iter->count + 1);
                                break;
                            }
                        }
                        if (iter == cc.end()) {
                            cc.push_back({ num, 1 });
                        }
                    }

                }
                sort(cc.begin(), cc.end(), sortCC);
                int rowNum = 0;
                for (iter = cc.begin(); iter != cc.end(); iter++) {
                    a[rowNum++][c] = iter->value;
                    a[rowNum++][c] = iter->count;
                }
                while (rowNum < maxR) {
                    a[rowNum++][c] = 0;
                }

                newMax = max(newMax, rowNum);
            }
            maxR = newMax;
        }

        /*cout << "result : " << result << " C : " << maxC << " R : " << maxR << endl;
        for (int r = 0; r < maxR; r++) {
            for (int c = 0; c < maxC; c++) {
                printf("%4d", a[r][c]);
            }
            cout << endl;
        }*/
    }


}

int main() {
    std::ios::sync_with_stdio(false);

    cin >> R >> C >> K;

    for (int r = 0; r < 3; r++) {
        for (int c = 0; c < 3; c++) {
            cin >> a[r][c];
        }
    }

    cout << solve();

    return 0;
}