[BOJ] 17140 : 이차원 배열과 연산

17140 : 이차원 배열과 연산

풀이

2019 삼성전자 SW역량테스트 기출문제 (오후)

시뮬레이션

DS지원한 나같은 경우 오전에 시험을 쳤고, 나머지가 오후에 친걸로 알고있는데 오후문제가 더 쉽다는 평이 많았다.

이 문제가 기출문제인지도 모르고 풀었다. 오전과 같은 시뮬레이션 유형이지만 시뮬레이션 안같고 기본문제 처럼 생겼기 때문이다.

문제에 적힌대로 R연산을 메모이제이션 기법을 사용하고, pair를 sorting한 후 조건에 맞게 예외처리 해서 값을 할당시켰다.

C연산은 R연산을 복사한후 배열 인덱스 순서만 바꿔주면 된다.

나는 pair를 sort하는 방식으로 조건에 맞는값을 쉽게 정렬시켰지만,

구조체를 사용하신분들은 sorting할때 ‘<’연산을 재정의 해주던지, cmp함수를 만드셔야 하는데

이부분을 잘 못하신분들이 많았다고 들었다. 편하신대로 하시면 될것같다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <cstring>
#include <queue>
using namespace std;

int arr[101][101];
int memo[101];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int r, c, k;
    cin >> r >> c >> k;
    int x = 3, y = 3;
    for (int i = 1; i <= x; i++) {
        for (int j = 1; j <= y; j++) {
            cin >> arr[i][j];
        }
    }
    
    int cnt = 0;
    while (cnt <= 100) {
        if (arr[r][c] == k) {
            cout << cnt;
            return 0;
        }
        //r연산
        if (x >= y) {
            int maxSize = 0;
            for (int i = 1; i <= x; i++) {
                memset(memo, 0, sizeof(memo));
                vector<pair<int,int>> vp;
                for (int j = 1; j <= y; j++) {
                    memo[arr[i][j]]++;
                }
                for (int j = 1; j <= 100; j++) {
                    if (memo[j] > 0) {
                        vp.push_back({memo[j],j});
                    }
                }
                sort(vp.begin(), vp.end());
                vector<int> v;
                for (auto x : vp) {
                    v.push_back(x.second);
                    v.push_back(x.first);
                }

                if (v.size() > maxSize ) {
                    if (v.size() > 100) {
                        maxSize = 100;
                    }
                    else {
                        maxSize = v.size();
                    }
                    int len = maxSize;
                    for (int j = 0; j < len; j++) {
                        arr[i][j + 1] = v[j];
                    }
                    for (int j = len; j < 100; j++) {
                        arr[i][j + 1] = 0;
                    }
                }
                else {
                    int len = v.size();
                    for (int j = 0; j <len; j++) {
                        arr[i][j + 1] = v[j];
                    }
                    for (int j = len; j < 100; j++) {
                        arr[i][j + 1] = 0;
                    }
                }
            }
            y = maxSize;
        }
        //c연산
        else {
            int maxSize = 0;
            for (int i = 1; i <= y; i++) {
                memset(memo, 0, sizeof(memo));
                vector<pair<int, int>> vp;
                for (int j = 1; j <= x; j++) {
                    memo[arr[j][i]]++;
                }
                for (int j = 1; j <= 100; j++) {
                    if (memo[j] > 0) {
                        vp.push_back({ memo[j],j });
                    }
                }
                sort(vp.begin(), vp.end());
                vector<int> v;
                for (auto x : vp) {
                    v.push_back(x.second);
                    v.push_back(x.first);
                }

                if (v.size() > maxSize) {
                    if (v.size() > 100) {
                        maxSize = 100;
                    }
                    else {
                        maxSize = v.size();
                    }
                    int len = maxSize;
                    for (int j = 0; j < len; j++) {
                        arr[j+1][i] = v[j];
                    }
                    for (int j = len; j < 100; j++) {
                        arr[j + 1][i] = 0;
                    }
                }
                else {
                    int len = v.size();
                    for (int j = 0; j <len; j++) {
                        arr[j + 1][i] = v[j];
                    }
                    for (int j = len; j < 100; j++) {
                        arr[j + 1][i] = 0;
                    }
                }
            }
            x = maxSize;
        }
        cnt++;
    }
    cout << -1;
    return 0;
}

Written on April 21, 2019