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

 

삼성 SW 기출문제이자 시뮬레이션 문제다.

이 문제를 풀면서 깨달은 것은 시뮬레이션 문제는 반드시 조건을 만족해야한다는 것이다.

그리고 꽤나 길기 때문에 메모하면서 문제를 해결하는 것이 좋다.

 

1초가 지날 때마다 연산을 해야한다.

정렬하는 연산은 수의 등장 횟수가 커지는 순으로 정렬하고,

그러한 수가 여러개면 수가 커지는 순으로 정렬한다.

 

R연산은 행의 개수가 열의 개수보다 크거나 같을 때 행단위로 정렬한다.

C연산은 열의 개수가 행의 개수보다 작을 때 열단위로 정렬한다.

 

열단위로 정렬해야하는 경우,

벡터를 탐색하면서 열 -> 행 으로 변경하여 정렬한다.

 

//열
2 1 1 2 0 0
1 1 2 1 3 1
3 3 0 0 0 0

//행
2 1 3 -> 정렬 -> 1 1 2 1 3 1
1 1 3 -> 정렬 -> 3 1 1 2
1 2 -> 정렬 -> 1 1 2 1
2 1 -> 정렬 -> 1 1 2 1
3 -> 정렬 -> 3 1
1 -> 정렬 -> 1 1

 

그리고 그 행에 대해 정렬을 완료 하고 탐색도 완료되었을 때,

다시 열 -> 행으로 변경하고, 빈 곳에 0을 추가한다.

 

1 3 1 1 3 1
1 1 1 1 1 1
2 1 2 2 0 0
1 2 1 1 0 0
3 0 0 0 0 0
1 0 0 0 0 0

 

수를 정렬할 때 0은 무시하여 정렬해야한다.

그리고 행 또는 열의 크기가 100을 넘어가는 경우, 처음 100개를 제외한 나머지는 버린다.

 

r,c,k가 주어졌을 때 

A[r][c] == k인 최소 시간을 출력해야하고,

100초가 지나도 만족되지 않을 경우 -1을 출력한다.

 

우선 이차원 벡터를 활용하여 문제를 풀었다.

아무래도 크기의 변동이 많은 문제이므로 벡터로 푸는 것이 가장 편할 것이라 판단했기 때문이다.

 

수의 등장 횟수가 커지는 순으로 정렬해야 하므로, 

해당 배열에 대한 탐색을 하면서,

100크기의 새 배열에 인덱스에 수를 집어넣고 그 수의 등장 횟수를 센다.

참고로 pair<int,int> 자료형을 이용하여 { 등장횟수, 인덱스 } 형태의 값을 대입했다.

그 후 수의 등장 횟수가 커지는 순으로 정렬하고, 동일할 경우 오름차 순으로 정렬한다.

 

vector<int> sortNum(vector<int> a){
    pair<int,int> number[101];
    for(int i = 1; i < 101; i++){
        number[i] = {0,0};
    }
    for(int i = 0; i < a.size(); i++){
        if(a[i] == 0) continue;
        number[a[i]] = {number[a[i]].first + 1, a[i]};
    }
    sort(number, number+101, compare);
    vector<int> answer;
    for(int i = 1; i < 101; i++){
        if(number[i].second > 0&& number[i].first > 0 && answer.size() < 100){
            answer.push_back(number[i].second);
            if(answer.size() < 100)
                answer.push_back(number[i].first);
        }
    }
    return answer;
}

 

정렬이 완료되면, 행 또는 열의 크기가 커진 경우, 빈 곳에 0을 삽입한다.

vector<vector<int>> addZero(vector<vector<int>> aVector){
    int maxIndex = getColumnCount(aVector);
            for(int i = 0; i < aVector.size(); i++){
                for(int j = 0; j < maxIndex; j++){
                    if(aVector[i].size() < j || aVector[i].size() == j){
                        aVector[i].push_back(0);
                    }
                }
            }
            return aVector;
}

 

열 -> 행으로 변경 후 정렬하고 빈 곳에 0을 삽입한다.

그리고 다시 열 -> 행으로 변경한다.

 

size_t columnCount = getColumnCount(a);
            vector<vector<int>> aVector;
            for(int i = 0; i < columnCount; i++){
                vector<int> columnVector;
                for(int j = 0; j < a.size(); j++){
                    columnVector.push_back(a[j][i]);
                }
                columnVector = sortNum(columnVector);
                aVector.push_back(columnVector);
            }
            aVector = addZero(aVector);
            a = rowToColumn(aVector, getColumnCount(aVector));

 

열 -> 행으로 변경하는 함수이다.

 

vector<vector<int>> rowToColumn(vector<vector<int>> a, int columnCount){
    vector<vector<int>> answer;
    for(int i = 0; i < columnCount; i++){
        vector<int> columnVector;
        for(int j = 0; j < a.size(); j++){
            columnVector.push_back(a[j][i]);
        }
        answer.push_back(columnVector);
    }
    return answer;
}

 

 

전체적인 코드는 이렇다.

 

//이차원 배열과 연산
#include <iostream>
#include<string.h>
#include <algorithm>
#include <vector>
using namespace std;
int r, c, k;
bool compare(pair<int,int> a, pair<int,int> b){
    if(a.first == b.first) return a.second < b.second;
    return a.first < b.first;
}
size_t getColumnCount(vector<vector<int>> a){
    size_t maxNum = 0;
    for(int i = 0; i < a.size(); i++){
        maxNum = max(maxNum, a[i].size());
    }
    return maxNum;
}
vector<int> sortNum(vector<int> a){
    pair<int,int> number[101];
    for(int i = 1; i < 101; i++){
        number[i] = {0,0};
    }
    for(int i = 0; i < a.size(); i++){
        if(a[i] == 0) continue;
        number[a[i]] = {number[a[i]].first + 1, a[i]};
    }
    sort(number, number+101, compare);
    vector<int> answer;
    for(int i = 1; i < 101; i++){
        if(number[i].second > 0&& number[i].first > 0 && answer.size() < 100){
            answer.push_back(number[i].second);
            if(answer.size() < 100)
                answer.push_back(number[i].first);
        }
    }
    return answer;
}
vector<vector<int>> rowToColumn(vector<vector<int>> a, int columnCount){
    vector<vector<int>> answer;
    for(int i = 0; i < columnCount; i++){
        vector<int> columnVector;
        for(int j = 0; j < a.size(); j++){
            columnVector.push_back(a[j][i]);
        }
        answer.push_back(columnVector);
    }
    return answer;
}
void print(vector<vector<int>> numVector){
    cout << "\n";
    for(int i = 0; i < numVector.size(); i++){
        for(int j = 0; j < numVector[i].size(); j++){
            cout << numVector[i][j] << " ";
        }
        cout << "\n";
    }
}
vector<vector<int>> addZero(vector<vector<int>> aVector){
    int maxIndex = getColumnCount(aVector);
            for(int i = 0; i < aVector.size(); i++){
                for(int j = 0; j < maxIndex; j++){
                    if(aVector[i].size() < j || aVector[i].size() == j){
                        aVector[i].push_back(0);
                    }
                }
            }
            return aVector;
}
int main(void){
    cin >> r >> c >> k;
    vector<vector<int>> a;
    for(int i = 0; i < 3; i++){
        vector<int> numVector;
        for(int j = 0; j < 3; j++){
            int num;
            cin >> num;
            numVector.push_back(num);
        }
        a.push_back(numVector);
    }
    int time = 0;
    while(1){
        if(a.size() > r-1 && a[r-1].size() > c-1 && a[r-1][c-1] == k){
            cout << time;
            break;
        }
        if(time == 100){
            cout << -1;
            break;
        }
        time++;
        if(a.size() > a[0].size() || a.size() == a[0].size()){
            vector<vector<int>> realA;
            for(int i = 0; i < a.size(); i++){
                realA.push_back(sortNum(a[i]));
            }
            a = addZero(realA);
        }
        else{
            size_t columnCount = getColumnCount(a);
            vector<vector<int>> aVector;
            for(int i = 0; i < columnCount; i++){
                vector<int> columnVector;
                for(int j = 0; j < a.size(); j++){
                    columnVector.push_back(a[j][i]);
                }
                columnVector = sortNum(columnVector);
                aVector.push_back(columnVector);
            }
            aVector = addZero(aVector);
            a = rowToColumn(aVector, getColumnCount(aVector));
        }
    }
}