백준 2075번 - N번째 큰 수: 약간 더 빠른 코드

문제

• 백준, 실버 3, https://www.acmicpc.net/problem/2075
• 풀이 날짜: 2025.2.4.
• 풀이 시간: 11:03~11:29(26분)
• 알고리즘 분류: 정렬, 우선순위 큐
• 사용 언어: C++

문제 해설

해당 문제는 상위 N번째 값을 구하는 문제이지만 두 가지 특징이 있다.

1. 메모리 제한이 걸려 있다. 12MB의 제한이 있다.
2. 모든 수는 자신의 한 칸 위의 수보다 더 크다.

첫 번째 특징을 생각해보면, 해당 문제는 NN (1≤N≤1500)의 보드가 주어지고 각 값의 절댓값이 10억보다 낮으므로 자료를 모두 저장하는 데에 최소 1,5001,5004Byte=2,250,0004Byte = 9,000,000Byte, 즉 약 9MB의 메모리가 필요하다.

이것만 해도 메모리 제한이 아슬아슬하므로, 만약 정렬을 통해 해결하려 한다면 메모리를 추가로 사용하지 않는 제자리 정렬을 사용해야 할 것이다.

메모리를 더 아끼기 위해서 표의 값을 저장하지 않고 상위 N개의 값만 남기는 식으로 PQ를 이용해 힙 정렬을 할 수도 있다. 하지만 두 번째 특징도 함께 생각해 보면, 이건 그리 좋지 않다.

두 번째 특징은 힙의 특성과 유사하다. 양 옆의 값은 전혀 관계가 없으며, 오로지 위, 아래에 있는 수 사이에만 대소 관계가 존재한다. 이를 좀 더 생각해 보자.

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

예제 입력으로 들어온 표이다.

가장 아래 행을 보면 52는 자신 위에 있는 값 48보다 크고, 20은 14보다 크고, 32는 28보다 크며, 다른 값들도 동일한 관계를 갖는다.

이때 N번째 큰 수를 찾아야 한다는 점을 생각해보면, 마지막 행에 있는 값이 위의 행보다는 크다고 했으니 N번째 큰 수도 마지막 행에 있을 것 같은 느낌이 든다.

하지만 이는 함정인데, 마지막 행 [52, 20, 32, 41, 49] 중 가장 작은 20은 다른 행에 있는 값 48보다 작고, 실제로 N번째, 즉 다섯 번째로 큰 수는 35이다.

다만 하나 알 수 있는 점은, 적어도 자신의 위에 있는 수보다는 크기 때문에 N번째로 큰 수는 마지막 행에서 가장 작은 숫자 20보다는 크거나 같을 것이라는 점이다.

[52, 20, 32, 41, 49]에서 48이 발견되면 20을 대체해서 48로 바꿔주고,

[52, 48, 32, 41, 49]에서 35가 발견되면 32를 대체해서 35로 바꿔줄 수 있다.

그러면 결과로 [52, 48, 35, 41, 49]가 나오는데, 위에 있는 행에서 조사 안 한 곳 중 35보다 더 큰 수가 없으므로 35가 5번째로 큰 수라 할 수 있다.

구체적인 알고리즘

좀 더 구체적으로 보자.

여기서는 가장 큰 수의 배열(ex: [52, 20, 32, 41, 49])에서 가장 작은 수보다 큰 값이 발견될 때마다 가장 작은 수를 대체하고 있다.

이 알고리즘은 최소 힙을 통해서 구현할 수 있다. C++에서는 우선순위 큐를 지원하니, Minimum Priority Queue, 줄여서 Min PQ를 활용하면 된다. 여기서 Min PQ란 값이 낮을수록 우선순위가 큰 큐를 말한다. 가장 큰 수의 배열을 Min PQ로 구현할 예정이다.

이때 N번째로 큰 수는 어느 열에 있을지는 알기 어렵다. 지금 가장 작은 수가 N번째로 작은 수거나, 아예 다른 열에 N번째로 작은 수가 있을 것이다.

나는 아예 단순하게, 각 열마다 아래에서 위로 순회하면서 N번째로 작은 수가 있는지 탐색하도록 했다. 단, (i, j)에서 현재 PQ에서 가장 작은 값보다 더 작은 값이 발견됐다면, i행보다 더 위에 있는 수는 (i, j)의 수보다 더 작을 것이므로 무시하도록 해야 한다.

예시로 한 번 예제 입력을 다시 보자.

12	7	9	15	5
13	8	11	19	6
21	10	26	31	16
48	14	28	35	25
52	20	32	41	49

초기에는 N번째 행의 값을 PQ로 활용한다. 이때 PQ는 최솟값을 계속해서 대체해 나갈 것이기 때문에 Min PQ로 구현한다.

[52, 20, 32, 41, 49]을 PQ에 삽입하고, 각 열을 돌면서 최솟값을 대체해 나갈 것이다. PQ에는 N개의 값만 남길 것이므로, 모두 순회한 후에 PQ에 남아 있는 최솟값이 N번째로 작은 값이 된다.

이제 각 열마다 순회해보자. 이때 순회할 땐 위보단 아래에 있는 값이 크기 때문에 (N-1)번째 행에서 1번째 행으로 순차적으로 올라가면서 찾는다.

초기에 PQ의 최솟값은 20이다.

1. col = 1

1) 48 → 48 > 20이므로 PQ에 삽입. 20은 제거한다(PQ = [52, 48, 32, 41, 49]). 이제 PQ의 최솟값은 32.

2) 21 → 21 < 32로 최솟값보다 작으므로 col=1은 더 큰 값을 찾을 수 없다.

2. col = 2

3) 14 → 14 < 32이므로 col = 2는 최솟값보다 더 큰 값을 찾을 수 없다.

3. col = 3

4) 28 → 28 < 32이므로 col = 3은 최솟값보다 더 큰 값을 찾을 수 없다.

4. col = 4

5) 35 → 35 < 32이므로 PQ에 삽입. 32는 제거한다(PQ = [52, 48, 35, 41, 49]). 이제 PQ의 최솟값은 35.

6) 31 → 31 < 35이므로 col = 4는 최솟값보다 더 큰 값을 찾을 수 없다.

5. col = 5

7) 25 → 25 < 35이므로 col = 5는 최솟값보다 더 큰 값을 찾을 수 없다.

잘 동작하는 것처럼 보인다. 이제 코드로 가보자.

Pseudo code

먼저 의사 코드로 정리하면 이렇다. mat의 인덱스는 1 ≤ row ≤ N, 1 ≤ col ≤ N이라 하자.

def N번째 큰 수(Mat):
    N번째 Row의 값을 모두 Min PQ에 삽입
    row <- N - 1
    while (mat[row][col] > Min PQ의 최솟값)
    {
        Min PQ에서 최솟값을 mat[row][col]로 대체
        row <- row - 1
    }
    return Min PQ의 최솟값

코드

의사 코드를 기반으로 코드를 구현하면 이렇게 된다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int mat[1500][1500];

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

    int N;

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> mat[i][j];
        }
    }

    // Min PQ 구현하기
    priority_queue<int, vector<int>, greater<int>> minPQ;

    // 마지막 행 PQ에 추가하기
    for (int col = 0; col < N; col++)
    {
        minPQ.push(mat[N-1][col]);
    }

    // column마다 가장 큰 값 추가하기
    for (int col = 0; col < N; col++)
    {
        int row = N - 2;

        // 아래에서 위로 올라가며 값 추가하기(PQ의 최소보다 작아질 때까지)
        while (row >= 0 && mat[row][col] > minPQ.top())
        {
            minPQ.pop();
            minPQ.push(mat[row][col]);
            row--;
        }
    }
    // Min PQ의 최솟값 = N번째로 작은 값
    cout << minPQ.top() << '\n';

    return 0;
}

이렇게 했을 때, 확실히 시간이 꽤 빠르게 나옴을 알 수 있다.

단순히 정렬하거나, 가장 큰 N개만 남기는 식으로 모든 배열을 순회해도 풀리긴 하지만, 이렇게 문제의 조건을 활용하면 약간 더 빠르게 해결할 수 있다.

사실 나 같은 사람보다 더 잘 해결한 사람들이 많으니 참고 용으로 봐주면 감사하겠다.