[알고리즘] 인덱스 해싱

코딩 테스트에서 가장 많이 사용하는 자료구조는 배열이다.

 

보통 배열을 사용할 때 인덱스로 데이터에 접근한다.

 

인덱스는 일반적으로 몇번째 데이터인지 나타내는 역할을 한다.

 

하지만 상황에 따라 인덱스에 해싱(hashing)개념을 적용하여 단순한 위치가 아니라 특정한 의미를 지닌 값으로 활용하면 문제 해결을 더 쉽게 할 때도 있다.

 

arr[1]의 의미

1. 몇 번째 데이터인지 순서를 의미하는 경우 → 첫 번째 데이터를 저장
2. 숫자값으로 의미를 부여하는 경우 → 1이라는 값이 몇 개 있는지를 저장

---

인덱스 해싱 적용 예시

예를 들어 1000보다 작은 자연수 10,000,000개를 1초 안에 정렬해야 하는 상황이라고 가정해보자.

 

데이터의 양이 많아서 일반적인 방법으로는 1초안에 정렬하기 어렵다.

하지만 인덱스를 값 자체로 활용하면 계수 정렬과 같은 방식으로 제한 시간 내에 정렬할 수 있다.

 

# 입력
10
10 9 8 7 6 5 4 3 2 1

import java.io.*;
import java.util.StringTokenizer

public class indexHashing{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(Sytem.out));
		
		int N = Integer.parseInt(br.readLine());
		int[] count = new int[1001];
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		for(int i = 0; i < N; i++){
			int number = Integer.parseInt(st.nextToken());
			count[number]++;
		}
		
		br.close();
		
		for(int i = 0; i <= 1000; i++){
			if(count[i] != 0){
				for(int i = 0; j < count[i]; j++){
					bw.write(i + " ");
				}
			}
		}
		bw.flush();
		bw.close();
	}
}

# 출력
1 2 3 4 5 6 7 8 9 10

 

여기서 count 배열의 인덱스에 숫자값으로 의미를 부여함으로 정렬 속도를 크게 향상 했다. 이렇게 하면 10,000,000개의 데이터를 1초 안에 정렬할 수 있다.

---

계수 정렬은 인덱스에 의미를 부여하는 좋은 예이다.

이처럼 인덱스에 의미를 부여하는 해싱 기법은 알고리즘으로 잘 체계화되어 활용되기도 한다.

하지만 실제 코딩 테스트에서는 요구사항에 따라 인덱스에 적절한 의미를 직접 부여해야 하는 문제도 자주 출제된다.

 

따라서 인덱스를 단순히 '몇 번째 순서'로만 생각하지 말고, 다양한 의미로 변환해 보는 것도 중요하다.

---

내용 출처

Do it! 알고리즘 코딩 테스트: 자바 편 | 김종관