값 자체를 배열의 인덱스로 쓰는 기법. 3이 나오면 cnt[3]을 하나 올린다. 비교를 한 번도 하지 않고 개수를 세거나 정렬할 수 있어서 O(N)에 끝난다. 비교 정렬의 n log n 하한을 넘어서는 방법이 이것이다.
세기와 계수 정렬
세는 것이 기본이다. 입력을 한 번 훑으며 cnt[값]++을 하면 어떤 값이 몇 번 나왔는지 즉시 알 수 있다.
세고 나서 인덱스 순으로 cnt[i]번씩 출력하면 정렬된 결과가 나온다. 이것이 계수 정렬이고, 100만 개를 정렬해도 O(N)이다.
짝 찾기를 O(N)으로
특정 값이 있었는지 O(1)에 확인하는 데도 쓴다. 이중 반복문으로 짝을 찾는 문제를 단일 반복문으로 내리는 자리에 자주 등장한다. 합이 X가 되는 두 수의 쌍을 세는 문제라면 각 값 a에 대해 X - a가 몇 개 있는지 O(1)에 알 수 있으니 O(N²)이 O(N)으로 내려간다. 다만 모든 쌍이 두 번씩 세어지므로 마지막에 2로 나누고, X의 절반까지만 돌면서 X가 짝수일 때 자기 자신과 짝이 되는 경우를 따로 처리해야 한다.
같은 문제를 투 포인터로도 푼다. 정렬을 하느냐 값의 범위에 기대느냐가 갈리는 지점이고, 두 접근을 고르는 기준은 그쪽에 정리해두었다.
음수 값 옮기기
배열 인덱스는 음수가 될 수 없으니, 값의 범위가 -1000부터 1000이면 전부 1000을 더해 0부터 2000으로 옮긴다. 꺼낼 때 다시 빼면 된다.
값의 범위에 걸리는 지점
시간을 공간과 맞바꾸는 기법이라 값의 범위가 작을 때만 성립한다. 값이 0부터 10억까지 나올 수 있다면 배열을 10억 칸 잡아야 하고, int라면 40억 바이트다. 애초에 못 잡는다. 문제에 “수의 범위는 10000 이하”처럼 범위가 명시되어 있으면 이 기법을 쓰라는 신호로 읽어도 좋다. 공간복잡도에서 막히는 자리다.
인덱스 범위 검사
계산한 값을 인덱스로 쓸 때 범위 검사를 빠뜨리면 그 자리에서 터진다. X - num을 인덱스로 쓰는데 그 값이 음수이거나 배열 크기를 넘을 수 있다. n이 1000이고 X가 500이면 X - num이 음수가 되는 경우가 실제로 생기니, 인덱스로 쓰기 전에 유효 범위인지 먼저 확인해야 ArrayIndexOutOfBoundsException이 나지 않는다.