[BOJ알고리즘, C++]#11004_K번째 수, nth_element 함수 활용

 

#1. 문제

11004번: K번째 수

 

---

 

#2. 풀이

 

1. nth_element 함수

void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last);
void nth_element (RandomAccessIterator first, RandomAccessIterator nth, RandomAccessIterator last, Compare comp);

 

[정의] : C++ 표준 라이브러리에서 제공하는 nth_element 알고리즘은 지정한 위치에 있는 원소가 배열을 정렬했을 때 그 위치에 있어야 되는 원소와 같아집니다. nth_element 알고리즘은 퀵 정렬에서 피벗 원소를 기준으로 왼쪽 배열과 오른쪽 부분 배열로 분할하는 방식과 동일합니다. nth_element 알고리즘은 선형 시간 복잡도를 가집니다.

 

2. nth_element로 정렬 후 k번째 원소를 출력한다.

1. 먼저, nth_element를 호출하고 지정 원소의 위치는 begin()+k-1로 설정해 줍니다.
2. 그리고, 배열의 K-1번째 원소를 출력하고 종료합니다.

 

---

 

#3. 코드

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

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

    int N, K;
    cin >> N >> K;

    vector<int> v(N);

    for (int i = 0; i < N; ++i)
        cin >> v[i];

    nth_element(v.begin(), v.begin() + K - 1, v.end());

    cout << v[K - 1];

    return 0;
}

 

---