[C++] 백준 17140번 이차원 배열과 연산

구현 / 정렬 / 시뮬레이션 문제.

삼성 S/W 기출문제 중 한 문제이다.

문제에 나온 그대로 구현하면 시간복잡도 고려할 필요없이 맞출 수 있다.

조건들이 생각보다 복잡하지만 골드4 구현 문제치고는 쉬운 편에 속한다고 생각한다.

정답 비율도 높은 걸 보면 쉽게 풀 수 있는 것 같다.

 

문제풀이

구현 문제는 문제에 나온 내용을 잘 정리하는 것이 중요하다.

문제의 내용을 간략하게 정리하면 다음과 같다.

• 배열 A의 최초 크기는 3x3이다.
• 그리고 1초마다 다음과 같은 연산을 한다.

1. 행의 길이 >= 열의 길이 일 경우, 배열 A의 모든 행을 정렬
2. 행의 길이 < 열의 길이 일 경우, 배열 A의 모든 열을 정렬

• 배열 A를 정렬하기 위해서는 각 수가 몇번 나왔는지 알아야 하고, 정렬의 우선순위는 다음과 같다.

1. 등장횟수가 작은게 앞에 오도록
2. 등장횟수가 같다면 작은 수가 앞에 오도록

• 정렬은 수, 등장횟수 와 같은 형태로 정렬이 된다. 예를 들어서 [1 1 2 3]을 정렬할 경우 [2 1 3 1 1 2]의 형태로 정렬이 된다.
• 수 정렬시, 0은 무시한다. 행 & 열의 크기가 100을 넘어갈 경우 처음 100개를 제외하고 나머지는 버린다.

 

입력에서 r, c, k가 주어질 경우 배열 A에서 A[r][c]가 k가 되는 최소 연산시간은 언제인지 구하면 된다.

만일 100초를 넘어갈 경우 -1을 출력하면 된다.

 

위 조건들을 코드로 구현만 해주면 된다.

 

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

int findR, findC, wantNum;
int row, column;
int curRow, curColumn;
vector<pair<int, int>> numVec; // 첫번째 등장횟수, 두번째 수
int numCnt[101][101];
int board[101][101];
int ans;

사용한 STL과 변수,

• findR, findC, wantNum : 입력받는 r, c, k이다.
• row, column : 현재 배열 A의 열(row) 길이와 행(column) 길이를 저장하는 변수이다.
• curRow, curColumn : 정렬하고난 후 바뀐 배열 A의 최대 열의 길이(curRow)와 최대 행의 길이(curColumn)를 저장하는 변수이다.
• numVec 벡터 : pair의 첫번째가 몇 번 등장하는지, 두번째가 어떤 수인지를 담는다. 이렇게 할 경우, 문제의 조건(1. 등장횟수 작은 것 + 2. 수 작은 것)에 맞게 sort STL 메서드를 사용해서 정렬할 수 있다.
• numCnt 배열 : 현재 행 또는 열 정렬을 할 때 1 ~ 100까지 수가 몇 번 나오는지 저장하는 배열이다.
• board 배열 : 배열 A의 정보를 담는 배열이다.
• ans : 만일 A[r][c]일 경우, 몇 초가 지났는지 출력하는 결과값이다.

 

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

    cin >> findR >> findC >> wantNum;

    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++) {
            cin >> board[i][j];
        }
    }

    column = 3;
    row = 3;

    go(0);

    if (board[findR][findC] == wantNum) { cout << ans; }
    else { cout << "-1"; }

    return 0;
}

메인함수.

 

처음에 r, c, k를 입력받는다.

후에 배열 A의 최초 값들을 입력받는다. 최초 크기는 3 x 3이다.

그리고 행 변수 column에 3을 넣고 열 변수 row에 3을 넣는다.

 

그리고 잠시 후에 설명할 go() 메서드를 호출한다. 매개변수 0은 0초가 지났다는 것을 알려주는 메서드이다.

 

만일 현재 배열 A의 A[r][c]가 k일 경우 ans를 출력하고, 아니라면 못 찾은 경우이므로 -1을 출력한다.

 

void go(int idx) {
    if (board[findR][findC] == wantNum) { ans = idx; return; }
    if (idx >= 100) { return; }

    if (column >= row) {
        curRow = 0;
        for (int i = 1; i <= column; i++) {
            columnSort(i);
        }
        row = curRow;

    }
    else {
        curColumn = 0;
        for (int i = 1; i <= row; i++) {
            rowSort(i);
        }
        column = curColumn;

    }

    go(idx + 1);
}

조건에 맞게 행 정렬 또는 열 정렬을 하는 메서드.

 

만일 현재 A[r][c] == k라면 ans에 idx를 저장하고 return한다.

또는 idx가 100초 이상일 동안 찾지 못했다면 그냥 return한다.

 

그리고 문제에 조건에 맞게 행의 길이 >= 열의 길이일 경우 행 정렬을 하는 columnSort()메서드를 호출한다. 매개변수로는 몇 번째 행인지를 넣어주면 된다.

행 정렬을 할 경우, 모든 행에 대해서만 확인하면 되므로 1 ~ column의 범위까지 정렬을 시도한다.

그리고 행 정렬을 하면 열의 길이가 늘어나거나 혹은 줄어드는데, 이를 갱신하기 위해서 curRow를 0으로 만들어놓고 각 행을 정렬할 때마다 현재 행에서의 열의 길이와 비교하면서 최대로 긴 열의 길이를 curRow에 넣고 배열 A의 열의 길이row 변수에 저장해주면 된다.

 

행의 길이 < 열의 길이일 경우 위 조건에서 열 정렬을 하는 rowSort()메서드를 호출한다. 진행내용은 위 내용에서 행-> 열을 바꾸기만 하면 된다.

 

void columnSort(int columnIdx) { // 행정렬
    memset(numCnt[columnIdx], 0, sizeof(numCnt[columnIdx]));
    numVec.clear();

    for (int i = 1; i <= row; i++) {
        int num = board[columnIdx][i];
        numCnt[columnIdx][num]++;
    }

    for (int i = 1; i <= 100; i++) {
        if (numCnt[columnIdx][i] != 0) {
            numVec.push_back({ numCnt[columnIdx][i], i });
        }
        board[columnIdx][i] = 0;
    }

    sort(numVec.begin(), numVec.end());

    int rowIdx = 1;
    for (pair<int, int> p : numVec) {
        int cnt = p.first;
        int num = p.second;
        board[columnIdx][rowIdx++] = num;
        board[columnIdx][rowIdx++] = cnt;
        if (rowIdx > 100) { break; }
    }

    curRow = max(curRow, rowIdx - 1);
}

void rowSort(int rowIdx) { // 열정렬
    memset(numCnt[rowIdx], 0, sizeof(numCnt[rowIdx]));
    numVec.clear();

    for (int i = 1; i <= column; i++) {
        int num = board[i][rowIdx];
        numCnt[rowIdx][num]++;
    }

    for (int i = 1; i <= 100; i++) {
        if (numCnt[rowIdx][i] != 0) {
            numVec.push_back({ numCnt[rowIdx][i], i });
        }
        board[i][rowIdx] = 0;
    }

    sort(numVec.begin(), numVec.end());

    int columnIdx = 1;
    for (pair<int, int> p : numVec) {
        int cnt = p.first;
        int num = p.second;
        board[columnIdx++][rowIdx] = num;
        board[columnIdx++][rowIdx] = cnt;
        if (columnIdx > 100) { break; }
    }

    curColumn = max(curColumn, columnIdx - 1);
}

행 정렬, 열 정렬 메서드.

 

행 정렬 기준으로 설명을 하자면 다음과 같은 순서로 진행된다.

1. 현재 numCnt[idx] 배열에 있는 모든 수들의 개수를 0으로 초기화한다.
2. numVec 벡터의 내용을 모두 지운다.
3. 현재 행에서 1열 ~ 최대 길이 열(row)까지 돌면서, 0이 아니라면 해당 수의 갯수를 1 증가시킨다.
4. 1 ~ 100까지 수의 개수가 0보다 큰 수가 있다면 numVec 벡터에 { 개수, 해당 수 }를 pair형태로 넣어놓는다. 그리고 1 ~ 100까지 행의 모든 수를 0으로 초기화시켜놓는다. 길이가 짧아질 때를 대비해서 0으로 초기화시켜 놓아야 한다.
5. 그리고 numVec 벡터를 sort 메서드로 정렬한다. { 개수, 해당 수 } 형태로 넣어놨으므로 문제에 조건에 맞게 정렬된다.
6. 현재 몇번째 열에 접근하는지 저장하는 변수 rowIdx를 1로 처음에 초기화하고, numVec의 사이즈만큼 수를 꺼내면서 board[현재 접근하는 행][rowIdx++]에 해당 수, 개수를 순차적으로 넣어준다. 이 때 만일 rowIdx가 100을 넘으면 나머지는 버리므로 for 반복문을 탈출한다.
7. curRow변수를 현재 curRow값과 (rowIdx- 1)중에 더 큰 값으로 갱신시켜준다. rowIdx에 -1을 하는 이유는, 현재 행의 열의 길이는 실제로는 rowIdx -1이기 때문이다.(rowIdx를 ++해줬기때문)

 

열 정렬은 위 정렬 기준으로 열로 바꿔주기만 하면된다. 배열에서 A[행][열] 이므로 이 부분을 잘 고려해줘서 구현해주면 된다.

 

처음에 cstring STL을 include하지 않아서 틀렸었다.

그 외에는 시간 제한이 0.5초임에도 바로 맞출 수 있었다.

 

연휴기간 동안 계속 코딩을 쉬었는데, (사실 나무 재테크란 문제를 풀다가 포기했었다. 나중에 다시 풀어봐야겠다.)

오랜만에 풀어서 그런지 머리가 잘 안돌아가는 느낌이였다.

연휴가 끝났으니까 진행중인 안드로이드 프로젝트도 다시 시작해야겠다...ㅜ

 

GitHub - kimyunseok/study-record: my study-record

코드 전문은 위에서 확인이 가능하다.