vector정렬시 변경된 index도 정렬하기

개요

코딩 테스트에서 주어진 벡터를 정렬한 후, 정렬된 벡터의 원래 인덱스를 활용해야 했다.
정렬이 이루어진 후에는 0번째, 1번째, 2번째 등의 인덱스가 임의의 순서로 섞이게 된다.
예) 3번째, 0번째, 2번째, 4번째, 1번째 ...
이 글에서는 벡터의 값을 정렬한 후, 원래 인덱스의 순서가 어떻게 변화하는지를 확인하는 방법을 소개한다.

핵심 코드 - itoa, sort + 람다함수의 사용

1. index를 저장할 벡터 indices를 주어진 벡터 크기만큼 생성한다.

   vector<int> v {4, 1, 3, 5, 2}; 
   vector<int> indices(v.size());  

2. iota함수를 이용해 0부터 1씩 증가한 인덱스를 저장한다.

   #include <numeric> 
   ... 
   iota(indices.begin(), indices.end(), 0); // {0, 1, 2, 3, 4}로 초기화

3. sort함수를 사용해 주어진 벡터와 람다함수를 입력하여 정렬한다.

   #include <algorithm>
   ...
   sort(indices.begin(), indices.end(),
       [&v](int a, int b) { return v[a] < v[b]; });

   a. [&v]

   외부 변수 v를 람다 함수 내에서 사용할 수 있도록 캡쳐하는 역할을 한다. & 기호는 해당 변수를 참조로 캡쳐한다는 의미다. 따라서, v의 내용이 변경되더라도 람다 함수에서 접근할 수 있다.  

   b. (int a, int b)

   람다 함수가 두 개의 정수 인덱스 a와 b를 입력받는다. 이 인덱스들은 정렬할 벡터 indices의 원소로 사용된다.  

   c. return v[a] < v[b];

   함수의 실제 동작을 정의한다. v[a]와 v[b]를 비교하여, v[a]가 v[b]보다 작으면 true를 반환하고, 그렇지 않으면 false를 반환한다. 이 조건에 따라 sort 함수는 인덱스 a와 b의 순서를 결정하게 된다.

예제 코드

#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

using namespace std;

int main() {
    vector<int> v {4, 1, 3, 5, 2};

    vector<int> indices(v.size());
    iota(indices.begin(), indices.end(), 0);

    sort(indices.begin(), indices.end(),
         [&v](int a, int b) { return v[a] < v[b]; });

    for (int index : indices) cout<<index<<" ";

    return 0;
}

실행 결과

참고 문헌

[C++] 람다 표현식, lambda에 대해서