백준 2075 N번째 큰 수

www.acmicpc.net/problem/2075

2075번: N번째 큰 수

이 문제는 정렬 또는 우선순위 큐를 통해 해결할 수 있다.

문제의 메모리 제한을 눈여겨 보자. 12MB로 평소와 다르다. int형 정수 1개는 4byte를 갖는다고 한다. 1천개면 4kb이고, 1백만개면 4MB이니 12메가 바이트는 겨우 3백만개의 정수만 담을 수 있는 것이다. 문제의 조건에서 N이 1500이므로 1500 x 1500 = 2,250,000 (225만)개의 정수가 필요하므로 다 담을 수 있을 것 같지만, 실제로는 이것 외에도 이것저것 다른 메모리가 더 필요하다. 따라서 조금 더 나은 풀이가 필요하다.

이 문제는 항상 N번째의 수를 알아야 하므로 이를 잘 활용해야 한다. N 크기의 우선순위 큐를 활용하거나 (실제N+1만큼 사용함), N 크기의 정렬된 배열을 사용하면 된다 (실제로는 2N만큼 사용함).

우선순위 큐(priority queue)는 max-heap과 min-heap의 2가지로 사용가능한데 필자의 C++코드는 min-heap을 사용했다. 우선순위 큐의 내부 구현에 대한 자세한 사항은 기회가 닿으면 다루도록 하겠다. 간단한게 설명하면, 우선순위 큐는 원소가 들어오거나(push) 나갈 때(pop) 내부 원소들을 정렬해준다. 그리고 log N의 시간이 소모된다. (N은 원소의 갯수) 따라서 갯수가 아주 많아도, 대단히 빠르게 정렬된 상태를 유지해주기 때문에 아주 유용하다. 구현 방법이나 자세한 내부 구조를 모른 채, 사용법만 알아도 아주 유용하게 쓸 수 있다.

 

문제에서는 첫 행에 12, 7, 9, 15, 5가 주어진다. 이를 그대로 우선순위 큐에 담는다. 그러면 그림에서와 같이, [5,7,9,12,15]와 같이 정렬된다. 

(우선순위 큐 내부구조는 트리구조를 이루고 있어서 정확하게 배열처럼 5,7,9,12,15의 선형구조를 갖지는 않는다! 다만 편의를 위해 저렇게 표현했을 뿐이다.)

그리고 다음 입력값을 하나씩 넣는다고 생각하면 위의 그림과 같이 6개로 늘어나고, 내부에서 정렬된다. 이제 가장 앞에 있는 가장 작은 수만 계속 버리면 되는 것이다. 

이 과정을 계속 반복하면 마지막에는 위와 같은 형태를 갖게 되고, 가장 앞에 있는 값만 출력해주면 된다. 

 

파이썬 코드에서는 리스트 간에 덧셈을 통해 합쳐줄 수 있고, 정렬 후 리스트 슬라이싱으로 N개만 취하는 방식을 사용했다.

위의 그림과 같이, 한 줄씩 입력을 받아서 리스트로 묶어주고 2개의 리스트를 합쳐준다.

그리고 정렬을 해주면(내림차순으로) 총 2N개의 원소가 정렬된다. 이중에 리스트 슬라이싱을 통해 앞에 있는 N개만 취하면 된다.

오름차순 정렬 후 뒤에 있는 N개를 취해도 똑같다.

배열의 크기는 최대 2N까지만 커지고 항상 그 중 N개만 취한다 그리고 이제 마지막 숫자를 취하면 된다 (오름차순 정렬했을 시에는 가장 앞에 있는 숫자)

 

<주요 내용>

정렬, 우선순위 큐, 맥스 힙, 미니멈 힙, 리스트 슬라이싱

 

<코드>

 

C++버전

#include <iostream>
#include <queue>
#define endl '\n'
using namespace std;

priority_queue<int, vector<int>, greater<int>> pq;
int n, k;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        if (i == 0)
        {
            for (int j = 0; j < n; ++j)
            {
                cin >> k;
                pq.push(k);
            }
        }
        else
        {
            for (int j = 0; j < n; ++j)
            {
                cin >> k;
                if (k > pq.top())
                {
                    pq.pop();
                    pq.push(k);
                }
            }
        }
    }
    cout << pq.top() << endl;
    return 0;
}

 

아래는 파이썬 코드이다

import sys
si = sys.stdin.readline


def main():
    n, l = int(si()), []
    for _ in range(n):
        l += [int(e) for e in si().split()]
        l = (sorted(l, reverse=True))[:n]
    print(l[n-1])


if __name__ == '__main__':
    main()