백준: 이차원 배열과 연산(17140번)

알고리즘 문제 해결 과정을 기록합니다

September 11, 2025 · 4 min read

문제 개요 #

Source: 백준 링크
Difficulty: Gold IV
Key Concept: 구현, 정렬, 시뮬레이션

접근 방법 #

배열에서 행과 열을 추출하여 임시 벡터에 저장 후, 문제에서 요하는 빈도 수에 맞게 정렬 후 각각의 빈도 수를 넣어 배열의 행고 열을 갱신하는 로직을 생각하였습니다. 이 때 정렬의 경우 map을 통해 각각의 빈도수를 정하고 pair를 타입으로 가지는 벡터를 통해 숫자와 빈도수를 정렬 후 다시 벡터에 정렬된 순서대로 숫자와 그 빈도수를 넣어 배열을 갱신하도록 하는 로직을 떠올렸습니다.

시행착오 #

100초 이내에 정렬을 통해 면하는 A[r][c] == k가 되지 않는다면 -1을 리턴해야 하기 때문에 반복문의 범위를 0 이상 100 미만으로 설정여 100번 반복되게 하였습니다. 그러나 해당 문제는 0초일 때, 즉 어떠한 연산도 하지 않은 경우부터 100초까지 즉 101번의 반복이 이루어져야 하기 때문에 실제는 초기 상태에서 한번 검사 후 100번의 반복을 통해 100초 이내에 r행 c열 위치에 원하는 k값이 나오는지 검사해야 했습니다.

해결 방법 #

const int TIME_LIMIT = 100;
const int SPACE_LIMIT = 100;
std::size_t row_size = 3, col_size = 3;
int r, c, k;
int board[110][110];

// 입력
void getInput() {
    std::cin >> r >> c >> k;
    r--;
    c--;
    for (std::size_t i = 0; i < row_size; ++i) {
        for (std::size_t j = 0; j < col_size; ++j) {
            std::cin >> board[i][j];
        }
    }
}

// 행 추출
vector<int> getRow(int row) {
    vector<int> r;
    for (int i = 0; i < col_size; i++) {
        r.emplace_back(board[row][i]);
    }
    return r;
}

// 열 추출
vector<int> getCol(int col) {
    vector<int> c;
    for (std::size_t row = 0; row < row_size; ++row) {
        c.emplace_back(board[row][col]);
    }
    return c;
}

// 정렬 연산 로직
void sortOperation(vector<int>& line) {
    map<int, int> count_map;
    vector<pair<int, int>> new_line;
    for (const auto& item : line) {
        if (item == 0) {
            continue;
        }
        count_map[item]++;
    }
    for (const auto& [k, v] : count_map) {
        new_line.emplace_back(k, v);
    }
    std::sort(new_line.begin(), new_line.end(),
              [](const pair<int, int>& a, const pair<int, int>& b) {
                  if (a.second != b.second) {
                      return a.second < b.second;
                  }
                  return a.first < b.first;
              });
    line.clear();
    for (const auto& p : new_line) {  // k: 수, v: 횟수
        line.emplace_back(p.first);
        line.emplace_back(p.second);
    }
}

// 100초 동안 정렬 연산을 통해 원하는 값 검사
int getOp() {
    if (r < row_size && c < col_size && board[r][c] == k) {
        return 0;
    }
    for (int i = 1; i <= TIME_LIMIT; i++) {
        if (row_size >= col_size) {
            for (std::size_t i = 0; i < row_size; ++i) {
                std::vector<int> line = getRow(i);
                sortOperation(line);  // line size == column
                col_size = std::max(col_size, line.size());
                for (int j = 0; j < col_size; j++) {
                    if (j >= SPACE_LIMIT) {  // 0~99까지 원소만 살림
                        break;
                    }
                    if (j < line.size()) {
                        board[i][j] = line[j];
                        continue;
                    }
                    board[i][j] = 0;
                }
            }
        } else {
            for (std::size_t i = 0; i < col_size; ++i) {
                std::vector<int> line = getCol(i);
                sortOperation(line);
                row_size = std::max(row_size, line.size());
                for (std::size_t j = 0; j < row_size; ++j) {
                    if (j >= SPACE_LIMIT) {
                        break;
                    }
                    if (j < line.size()) {
                        board[j][i] = line[j];
                        continue;
                    }
                    board[j][i] = 0;
                }
            }
        }
        if (r < row_size && c < col_size && board[r][c] == k) {
            return i;
        }
    }
    return -1;
}


int solution() {
    getInput();
    return getOp();
}

알고리즘 설명 #

초기 값을 검사한 다음 100번의 반복에서 행보다 열이 크거나 같다면 행 정렬 연산이, 열이 크다면 열 정렬 연산이 반복되도록 하였습니다.

이 때 각 연산은 행 또는 열을 getRow또는 getCol을 통해 추출 후 정렬 연산 로직으로 참조 매개 변수로 넣었습니다. 각각 숫자의 빈도를 체크하기 위해 map을 통해 수가 나올 때마다 value값을 증가시키고, pair타입수 벡터에 통해 각 수와 빈도 수 페어를 입력시킨 후 이를 sort를 통해 빈도수를 기준으로 오름 차순으로 정렬하였습니다. 마지막으로 pair를 다시 쪼개 숫자와 빈도수를 모두 원래 line 벡터에 넣어 board를 갱신시킬 수 있게 하였습니다.

이 후 반복문을 통해 board의 값을 갱신시키고 이를 모든 행 또는 열에 적용 후, 행 또는 열의 크기를 갱신 그리고 나머지 100초 동안의 반복문이 진행되도록 하였습니다.

성능 분석 #

Time Complexity: $O(N^2\log N)$

핵심 정리 #

구조적으로 문제를 바라보면서 조건과 경계값들에 대해서 주의가 필요한 문제였습니다. 복잡하거나 어려운 알고리즘 지식이 필요하지는 않았지만 시간을 반복문으로 표현할 때의 경계 조건의 중요성을 생각하게 됩니다.