이번 글에서는 C++에서 pair(쌍)의 벡터를 활용해 주어진 배열을 축소된 형태(reduced form)로 변환하는 프로그램을 단계별로 알아보겠습니다.
문제 정의
하나의 배열이 주어졌을 때, 이 배열을 0부터 n-1 사이의 값만 포함하도록 변환하는 것이 목표입니다. 여기서 말하는 '축소된 형태'란 배열의 각 요소를 원래 값 대신 상대적인 크기 순위로 바꾼 결과를 뜻합니다. 가장 작은 값은 0, 두 번째로 작은 값은 1과 같은 식으로 매핑됩니다.
알고리즘 동작 원리
전체 구현은 세 단계로 이루어집니다.
- pair 생성: 각 배열 요소를 '값 + 원래 인덱스'가 함께 담긴 pair로 만들어 벡터에 저장합니다.
- 정렬: 벡터를 요소 값 기준으로 오름차순 정렬합니다.
- 순위 할당: 정렬된 순서를 참조해 각 요소의 원래 인덱스 위치에 새로운 순위(0~n-1)를 기록합니다.
pair에 원래 인덱스를 함께 보관하기 때문에 정렬 후에도 각 값이 어느 위치에 있었는지 추적할 수 있고, 이를 통해 별도의 결과 배열 없이 원본 배열을 곧바로 갱신할 수 있다는 점이 이 기법의 핵심입니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 배열을 축소된 형태로 변환하는 함수
void convert(int arr[], int n){
// pair의 벡터 생성
vector <pair<int, int> > v;
// 값과 함께 인덱스도 저장
for (int i = 0; i < n; i++)
v.push_back(make_pair(arr[i], i));
// 값 기준 오름차순 정렬
sort(v.begin(), v.end());
// 정렬된 순서대로 원래 위치에 순위 기록
for (int i = 0; i < n; i++)
arr[v[i].second] = i;
}
// 배열 출력 함수
void print_array(int arr[], int n) {
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
}
int main(){
int arr[] = {10, 20, 15, 12, 11, 50};
int n = sizeof(arr)/sizeof(arr[0]);
cout << "Given Array is :\n";
print_array(arr, n);
convert(arr , n);
cout << "\nConverted Array:\n";
print_array(arr, n);
return 0;
}실행 결과
Given Array : 10 20 15 12 11 50 Converted Array: 0 4 3 2 1 5
결과 분석
원본 배열 {10, 20, 15, 12, 11, 50}에서 10이 가장 작으므로 0으로, 11은 두 번째로 작으므로 1로, 이후 12→2, 15→3, 20→4, 50→5 순으로 변환됩니다. 이처럼 각 요소의 상대적 순위는 그대로 유지되면서 배열 전체가 0~n-1 범위의 값으로 깔끔하게 압축됩니다.
복잡도 분석
핵심 연산이 정렬이므로 시간 복잡도는 O(n log n)이며, pair를 저장하기 위한 벡터로 인한 추가 공간 복잡도는 O(n)입니다. 요소의 실제 값보다 상대적 순위가 중요한 좌표 압축(coordinate compression) 문제에서 널리 활용되는 패턴이니 꼭 익혀두시길 권합니다.