[알고리즘 #1] 인덱스에 의미 부여하여 풀어 보기

도경원

Aug 23, 2025

Contents

계수 정렬

인덱스는 일반적으로 ‘몇 번째 데이터인지’ 나타내는 역할을 한다. 하지만 상황에 따라 해싱 개념을 적용하여 단순한 위치가 아니라 특정한 의미를 지닌 값으로 활용하면 문제를 더 쉽게 해결할 수 있다.

그중에 인덱스를 순서가 아닌 해당 숫잣값 자체에 의미를 부여하는 상황을 가장 자주 사용한다.

💬

A[1]의 의미

몇 번째 데이터인지 순서를 의미하는 경우 → 첫 번째 데이터를 저장한다.

숫잣값으로 의미를 부여한 경우 → 1이라는 값이 몇 개 있는지를 저장한다.

계수 정렬


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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.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 j = 0; j < count[i]; j++) {
					bw.write(i + " ");
				}
			}
		}
		bw.flush();
		bw.close();
	}
}

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