데이터 이산화는 본질적으로 해시(Hash)의 한 형태로, 데이터 자체의 값보다는 순위(Rank)가 중요할 때 사용됩니다. 값의 범위가 넓고 희소한 데이터를 더 좁은 범위로 매핑하는 기법입니다.

주로 두 가지 방식으로 구현됩니다: sort + unique 조합과 map을 활용하는 방법입니다.

sort + unique 방식

배열을 정렬한 후 중복을 제거합니다. 모든 필요한 값을 하나의 배열에 담아 정렬한 뒤, 중복된 값을 제거합니다. 데이터는 정렬된 상태를 유지하며, 인덱스가 이산화된 값이 됩니다. 검색은 lower_bound를 사용합니다.

정렬 및 중복 제거

for(int i = 1; i <= n; i++) original[i] = arr[i]; // 원본 배열 복사
sort(original + 1, original + n + 1);
int distinctCount = unique(original + 1, original + n + 1) - original - 1;

unique 함수는 중복이 제거된 시퀀스의 마지막 요소 다음 위치를 가리키는 반복자를 반환합니다. 따라서 시작점과의 차이로 중복되지 않은 요소의 개수를 구할 수 있습니다.

값 검색

int index = lower_bound(original + 1, original + distinctCount + 1, target) - original;

original 배열에서 target 값보다 크거나 같은 첫 번째 요소의 위치를 찾아 이산화된 값을 반환합니다.

전체 매핑

int mapped[N];
for (int i = 1; i <= n; i++) {
    mapped[i] = lower_bound(original + 1, original + distinctCount + 1, arr[i]) - original;
}

원본 시퀀스의 모든 값을 매핑합니다. 예를 들어 arr = {12, 32, 56, -1, 35, 32}라면, 매핑 후 mapped = {2, 3, 5, 1, 4, 3}이 됩니다.

map 활용 방식

map을 사용하면 정렬, 중복 제거, 검색, 매핑을 한 번에 처리할 수 있습니다. map은 내부적으로 레드-블랙 트리로 구현되어 있으며, 다양한 타입을 키로 사용할 수 있는 연관 배열입니다.

주요 기능:

• map<KeyType, ValueType> myMap;: 키 타입이 KeyType, 값 타입이 ValueType인 맵 선언
• myMap[key] = value: 특정 키에 값 할당
• myMap[key]: 키에 해당하는 값 접근
• myMap.end(): 마지막 요소 다음 위치의 반복자
• myMap.empty(): 맵이 비었는지 확인
• myMap.size(): 요소 개수 반환
• myMap.erase(key): 특정 키의 요소 삭제
• myMap.find(key): 키 검색, 없으면 myMap.end() 반환

이산화 구현 예시:

map<int, int> valueToRank;
int rank = 0;
sort(arr + 1, arr + n + 1);
for (int i = 1; i <= n; i++) {
    if (i == 1 || arr[i] != arr[i-1]) {
        valueToRank[arr[i]] = ++rank;
    }
}
int targetRank = valueToRank[target]; // 검색

이 방식은 문자열 등 다른 타입의 이산화에도 쉽게 적용할 수 있습니다.

더 간결한 범용 구현:

map<int, int> rankMap;
int nextRank = 0;
int getRank(int x) {
    if (rankMap.count(x) == 0) {
        rankMap[x] = ++nextRank;
    }
    return rankMap[x];
}
for (int i = 1; i <= n; i++) {
    arr[i] = getRank(arr[i]);
}

map의 키 타입은 필요에 따라 자유롭게 변경 가능합니다.