N번째 큰 수 찾기 (std::nth_element)

C++을 사용하면서 N번째로 큰 숫자를 찾아야 하거나 중앙 값을 찾아야 할 때, sort로 정렬하여 인덱스로 접근하는 방식도 있지만, 배열의 원본을 건드리지 않고 더 효과적으로 찾는 방법이 있다.

 

1. nth_element 함수는

• C++ 표준 라이브러리(STL)의 <algorithm> 헤더에 포함된, 특정 범위(range) 내의 요소를 재배열하는 아주 유용한 알고리즘.
• N번째 요소가 마치 전체가 정렬되었을 때의 그 위치에 오도록 보장해주는 함수이다.
• 내가 지정한 nth 위치의 요소가 '정렬된 상태'의 N번째 값과 같아지도록 바꿔준다.
• nth 위치를 기준으로 범위가 대력적으로 두 부분으로 나뉜다
  • nth 위치보다 앞에 있는 모든 요소들은 nth 요소보다 작거나 같다.
  • nth 위치보다 뒤에 있는 모든 요소들은 nth 요소보다 크거나 같다.
• 전체를 다 정렬하는게 아니라 딱 n번째에 해당하는 원소만 자기 자리에 찾아주고, 그 앞뒤로는 '앞은 작은 원소들, 뒤는 큰 원소들'이라는 느낌으로 대충 정리해주고 순서는 보장하지 않는다. n번째 요소만 알면 되는 상황에서 엄청 효율적인 함수이다.

2. 장점

• sort는 모든 요소를 제자리에 놓으려고 하기에 복잡도가 높다.
• nth_element는 단지 n번째 요소를 제자리에 놓는 것에 집중하기 때문에, 평균적으로 훨씬 빠른 시간 복잡도를 가진다.

 

3. 사용법

#include <algorithm> 
#include <vector>
#include <functional> // std::greater<int>()를 쓰려면 필요

void nthElement_usage_example() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 4, 7, 3, 6};

    // 예시 1: 3번째로 작은 숫자를 찾고 싶다 (인덱스는 0부터 시작하니까 '2'번째)
    // numbers.begin()부터 numbers.end() 범위에서, numbers.begin() + 2 위치에
    // 3번째로 작은 숫자가 오도록 해야한다
    std::nth_element(numbers.begin(), numbers.begin() + 2, numbers.end());
    // 이 시점에서 numbers[2]에는 3번째로 작은 숫자(여기서는 '3')가 들어있다
    // numbers[0], numbers[1]은 3보다 작거나 같은 값들이고,
    // numbers[3] 이후는 3보다 크거나 같은 값들이다. (순서 보장은 안 됨)

    // 예시 2: 3번째로 큰 숫자를 찾고 싶다면?
    // 기본적으로는 오름차순 기준으로 작동하기 때문에, 내림차순으로 바꾸려면
    // 세 번째 인자에 비교 함수(comparator)를 넣어주면 된다
    std::vector<int> another_numbers = {5, 2, 8, 1, 9, 4, 7, 3, 6};
    std::nth_element(another_numbers.begin(), another_numbers.begin() + 2, another_numbers.end(), std::greater<int>());
    // 이제 another_numbers[2]에는 3번째로 큰 숫자(여기서는 '7')가 들어있다
    // 앞은 7보다 크거나 같고, 뒤는 7보다 작거나 같은 값들로 재배열되어 있다
}

• 첫 번째 인자(first) : nth_element를 적용할 범위의 시작을 가리키는 반복자.
• 두 번째 인자(nth) : 우리가 찾고자 하는 'N번째' 요소가 놓일 위치를 가리키는 반복자. 만약 3번째 요소를 원하면 begin()+2
• 세 번째 인자(last) : 범위의 끝을 가리키는 반복자
• 네 번째 인자(compare_fuction) : 기본적으로 오름차순인데 내림차순으로 N번째 값을 찾고 싶을 때처럼, 비교 기준을 바꿔주고 싶을 때 사용. std::greater<int>() 를 사용 하여 내림차순 정렬을 한다. 사용 시 <fucntional> 헤더 추가 필요.