[C/C++] 백준 #2075 N번째 큰 수(n'th element)

 N번째 큰 수를 찾으라는 이 문제는 특이한 조건을 가진 \(N \times N\) 2차원 공간에 들어가 있는 숫자 중 뒤에서 N번째 큰 수를 찾아서 출력하라는 것입니다.

 

https://www.acmicpc.net/problem/2075

2075번: N번째 큰 수

 

처음 이 문제를 봤을 때, 저 조건을 잘 이용하면 되지 않을까라는 생각을 하고 고민을 했습니다.  하지만 결론은 문제에서 제시하는 조건은 쓸모가 없다는 것입니다.  N개의 정렬된 상태의 배열이 있으니 합병을 생각할 수도 있지만, 결국 \(O(N^2)\)이고, 데이터를 읽는데 이미 \(O(N^2)\)이라서 의미가 크게 있지 않습니다.

 

이 문제를 풀기 위한 가장 간단한 방법은 정렬을 사용한 후, 뒤에서 N번째 숫자를 출력하는 것입니다.  정렬을 사용하면 시간복잡도는 \( O(N^2 \log N) \) 입니다.  공간 복잡도는 \( O(N^2) \) 입니다.

 

두번째 방법은 N개의 큰 수를 유지하는 우선순위큐를 사용하는 것입니다.  시간복잡도는 \(O(N^2 \log N)\) 으로 정렬과 같습니다.  공간 복잡도는 \( O(N) \) 입니다.  만약 공간복잡도 제한이 강하게 있었다면 이 방법을 선택해야 합니다.

 

세번째 방법은 nth element 알고리즘을 이용하는 방법입니다.  정렬을 쓰는 것보다 이것이 더 좋습니다.  시간복잡도는 \( O(N^2) \)으로 가장 좋습니다.  공간 복잡도는 정렬과 같은 \( O(N^2) \) 입니다.

 

nth element는 퀵정렬의 파티션을 사용한 알고리즘입니다.

nth element algorithm

 

파이썬에서는 nth element를 사용하는 함수가 없어서 정렬 후 진행하면 됩니다.

 

제가 작성한 소스입니다.

//----------------------------------------------------------
//    baekjoon #2075 - Nth Biggest Number
//        - by Aubrey Choi
//        - created at 2020-01-13
//----------------------------------------------------------
#include <cstdio>
#include <algorithm>

int main()
{
    static int v[1500*1500];
    int n, i;
    scanf("%d",&n);
    for(i=0;i<n*n;i++) scanf("%d", v+i);
    std::nth_element(v, v+n*(n-1), v+n*n);
    printf("%d\n", v[n*(n-1)]);
}