[백준(BOJ)] 11004번: K번째 수 (정렬, C++)

📄 문제풀이 과정

---

오름차순 정렬 후 K번째 위치한 수를 출력하는 문제이다.

간단하게 qsort로 정렬 후 0번째부터 시작하므로 K-1 인덱스의 숫자를 출력하면 되겠다고 생각했는데, 런타임 에러가 발생해서 찾아보니 Quick Selection Sort를 이용하여 좀더 효율적인 알고리즘을 사용해야 해결할 수 있음을 알 수 있었다.

Quick Selection 알고리즘은 임의의 숫자 배열에서 K번째로 작거나 큰 값을 찾을 때 사용하는 알고리즘으로, 모든 배열을 정렬하는 것이 아니라 partition 함수의 리턴 값과 K를 비교하여 partition을 나눌지 결정하는 방식으로 K번째 수를 찾는다.

Quick Sort의 경우 평균  O(nlogn), worst case에 O(n^2)이지만, Quick Selection Sort는 worst case에도 시간복잡도가 O(n)이다.

C++에서는 nth_element가 Quick Selection 알고리즘과 같이 동작한다고 하여 nth_element로 정렬 후 K-1 인덱스의 수를 출력하여 문제를 풀었다.

 

💻 코드

---

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, K;
    scanf("%d %d", &N, &K);
    deque<int> A;
    for(int i=0; i<N; i++){
        int num; scanf("%d", &num);
        A.push_back(num);
    }
    
    //qsort(&A[0], A.size(), sizeof(int), compare);
    nth_element(A.begin(), A.begin() + K -1, A.end());
    //for(int i : A) cout << i << " ";
    //cout << endl;
    printf("%d", A[K-1]);
}

 

🖨 제출 결과

---