[C++] 이차원 배열과 연산 (17140번)

이차원 배열과 연산

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

0.5 초 (추가 시간 없음)

512 MB

18892

8867

5795

43.925%

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

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

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

---

문제풀이

 

요즘 빡 구현문제를 많이 풀고 있는데 점점 풀면서 도식화 하는 실력이 올라가는것 같다. 또 구현문제 같은 경우는, main 함수에 모든 코드를 몰아넣는것 보단 함수로 빼서 구현하는것이 더 좋다고 생각한다. 어디서 틀렸는지 찾기 더 쉽고 각 기능이 분리되어 있어 그것에만 집중할수 있어 코드작성도 더 빠른것같다.

 

처음에 문제가 잘 이해가 안됐는데 그냥 각 연산별로

등장 횟수 오름차순

같은경우 숫자 크기 오름차순

으로 정렬하란 얘기다.

 

r 연산, c 연산 각각 함수를 정의해주었다.

또 각 크기를 알아야 한다고 생각해 r_size, c_size 변수를 정의해 각각 3으로 초기화 해주었다. 이때 주의할점이 r연산을 하면 c_size의 값이 바뀌고 c연산을 하면 r_size의 값이 바뀐다.

 

행 연산을 먼저 보자.

map을 사용해 각 행에 나온 숫자를 key로하고 나온 횟수를 value로 한다.

이것을 vector에 pair형태로 넣어 위에 언급한 기준으로 정렬해준다.

그리고 vector에 넣은 값들을 배열에 적용시키면 끝이다.

 

3줄요약 끝!!! 이제 구현하면 된다.

 

조금 더 자세한 설명을 원한다면 이 글을 마저 읽어보자.

행 연산 함수에 대한 구체적인 설명이다.

우선, c_size값을 바꿔야 하기 때문에 바뀐 c_size 값을 저장할 변수하나를 선언한다. 반복문을 돌면서 각 행에대한 연산을 진행할 텐데 가장 큰값을 넣어주면 된다.

 

반복문을 돌며 행의 값들을 map에 담는다. map을 반복돌면서 vector<pair<int, int>>를 하나 선언한 뒤 first는 숫자, second는 나온 횟수를 저장한다.

 

이 vector를 기준에 맞게 정렬한다.

반복문을 돌면서 배열을 수정한다.

v의 값이 100보다 작다면 나머지 값들은 0을 넣어주게 하였다.

 

c_size의 값을 변경한다.

 

끝!

 

이와 같은 방식으로 c연산도 해주면 된다.

중간 중간 코드 작성하면서 오타, 헷갈리는것 때문에 어디가 틀렸는지 확인하느라 시간이 오래걸렸다. 이 점만 주의한다면 구현문제 푸는 속도를 상당히 높힐수 있다고 생각한다.

어디가 틀렸는지 찾는덴 항상 오래걸리기 때문에 애초에 시간이 걸리더라도 처음에 작성할때 똑바로 작성하는게 좋다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

int arr[101][101];
int r_size = 3, c_size = 3;
int r, c, k;

bool cmp(pair<int, int> &a, pair<int, int> &b) {
    if(a.second < b.second) return true;
    if(a.second == b.second && a.first < b.first) return true;
    return false;
}

void cal_r() {
    // 행 개수 최대값
    int m = 0;
    for(int i=1; i<=r_size; i++) {
        unordered_map<int, int> um;
        for(int j=1; j<=c_size; j++) {
            if(arr[i][j] == 0) continue;
            um[arr[i][j]]++;
        }
        // 숫자, 등장 횟수
        vector<pair<int, int>> v;
        for(auto iter=um.begin(); iter != um.end(); iter++) {
            v.push_back({iter->first, iter->second});
        }
        m = max(m, int(v.size())*2);
        sort(v.begin(), v.end(), cmp);

        for(int j=0; j<v.size(); j++) {
            // 100 초과인 경우
            if(j >= 50) break;
            arr[i][j*2+1] = v[j].first;
            arr[i][j*2+2] = v[j].second;
        }
        // 0 으로
        for(int j=v.size()*2+1; j<=100; j++) {
            arr[i][j] = 0;
        }
    }
    c_size = min(100, m);
}

void cal_c() {
    // 열 개수 최대값
    int m = 0;
    for(int i=1; i<=c_size; i++) {
        unordered_map<int, int> um;
        for(int j=1; j<=r_size; j++) {
            if(arr[j][i] == 0) continue;
            um[arr[j][i]]++;
        }
        // 숫자, 등장 횟수
        vector<pair<int, int>> v;
        for(auto iter=um.begin(); iter != um.end(); iter++) {
            v.push_back({iter->first, iter->second});
        }
        m = max(m, int(v.size()*2));
        sort(v.begin(), v.end(), cmp);

        for(int j=0; j<v.size(); j++) {
            // 100 초과인 경우
            if(j >= 50) break;
            arr[j*2+1][i] = v[j].first;
            arr[j*2+2][i] = v[j].second;
        }
        // 0 으로
        for(int j=v.size()*2+1; j<=100; j++) {
            arr[j][i] = 0;
        }
    }
    r_size = min(100, m);
}

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

    for(int i=0; i<101; i++) {
        if(arr[r][c] == k) {
            cout << i;
            return 0;
        }

        if(r_size >= c_size) {
            cal_r();
        }
        else {
            cal_c();
        }

        // for(int a=1; a<=5; a++) {
        //     for(int b=1; b<=5; b++) {
        //         cout << arr[a][b] << " ";
        //     }
        //     cout << endl;
        // }
        // cout << r_size << " " << c_size;
        // cout << endl;
    }

    cout << -1;
    return 0;
}