개요
이 글에서는 해싱(hash) 기법을 활용해 배열을 축소 형태(reduced form)로 변환하는 C++ 프로그램을 다룹니다.
여기서 축소 형태란 주어진 배열의 모든 요소를 0부터 n-1 사이의 값으로 바꾸는 것을 의미합니다. 이때 각 요소는 원래 배열 안에서의 크기 순서(순위)를 그대로 유지합니다. 즉, 가장 작은 요소는 0, 두 번째로 작은 요소는 1로 변환되는 방식입니다.
접근 방법
알고리즘의 동작 과정은 다음과 같습니다.
- 원본 배열의 복사본을 만든 뒤 오름차순으로 정렬합니다.
- 정렬된 배열을 순회하면서 각 요소를 키(key)로, 0부터 하나씩 증가하는 값을 밸류(value)로 저장하는 해시 테이블(
unordered_map)을 구성합니다. - 원본 배열의 각 요소를 해시 테이블에서 조회하여 해당 순위 값으로 치환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
// 배열을 축소 형태로 변환하는 함수
void convert(int arr[], int n){
// 배열 요소 복사
int temp[n];
memcpy(temp, arr, n*sizeof(int));
sort(temp, temp + n);
// 해시 테이블 생성
unordered_map<int, int> umap;
int val = 0;
for (int i = 0; i < n; i++)
umap[temp[i]] = val++;
// 해시 테이블의 값을 이용해 원본 배열 변환
for (int i = 0; i < n; i++)
arr[i] = umap[arr[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 :\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, 11, 12, 15, 20, 50}이 됩니다. 이때 해시 테이블에는 다음과 같은 매핑 정보가 저장됩니다.
- 10 → 0
- 11 → 1
- 12 → 2
- 15 → 3
- 20 → 4
- 50 → 5
원본 배열의 각 요소를 이 매핑에 따라 치환하면 최종적으로 0 4 3 2 1 5라는 축소 형태의 배열을 얻게 됩니다.
복잡도 분석
- 시간 복잡도: O(n log n) — 배열 정렬에 지배적인 영향을 받습니다.
- 공간 복잡도: O(n) — 복사본 배열과 해시 테이블을 위해 추가 메모리가 필요합니다.