계수·버킷 정렬

언제 쓰나

정렬 기준이 되는 수의 범위가 작고 정해져 있을 때 씁니다. 그 수를 배열의 번호로 바로 쓸 수 있으면, 값끼리 비교하지 않아도 순서가 정해집니다.

• “가장 많이 나온 k개”, “빈도순”처럼 등장 횟수로 순서를 매깁니다. 횟수는 1부터 배열 길이 n 사이에 있어서 번호로 쓰기 좋습니다.
• 값 자체의 범위가 좁습니다. 0~100점 시험 점수나 알파벳 26자처럼 값을 그대로 번호로 쓸 수 있는 경우입니다.
• 문제가 O(n log n)보다 빠른 풀이를 요구합니다. 아래 대표 문제의 추가 조건(Follow up)이 이 경우입니다.

어떻게 동작하나

정렬로 풀면

LeetCode 347은 정수 배열 nums에서 가장 많이 나온 값 k개를 돌려주는 문제입니다. nums = [1, 1, 1, 2, 2, 3], k = 2라면 1이 3번, 2가 2번, 3이 1번 나오므로 [1, 2]가 답입니다.

손으로 풀면 두 단계를 거칩니다.

1. 값마다 몇 번 나왔는지 셉니다. 1은 3번, 2는 2번, 3은 1번입니다.
2. 횟수가 큰 순서로 값을 줄 세운 뒤 앞에서 k개를 고릅니다.

2단계를 sort로 하면, 서로 다른 값이 m개일 때 값끼리 비교해 줄 세우는 데 O(m log m)이 들어 전체는 O(n + m log m)입니다. 값이 모두 다르면 m = n이라 O(n log n)이 됩니다. 값끼리 비교해서 순서를 정하는 정렬은 이보다 빨라질 수 없기 때문에, 이 문제의 추가 조건인 “O(n log n)보다 빠르게”를 맞추려면 비교하지 않고 순서를 정하는 방법이 필요합니다.

빈도를 버킷 번호로 쓴다

횟수에는 범위가 있습니다. 어떤 값도 nums의 길이인 6번보다 많이 나올 수는 없습니다. 그래서 0번부터 6번까지 번호를 붙인 버킷(bucket) 7개를 늘어놓고, 값을 자기가 나온 횟수와 같은 번호의 버킷에 넣습니다. 1은 3번 나왔으니 3번 버킷, 2는 2번 버킷, 3은 1번 버킷에 들어갑니다.

빈도별 버킷 · nums = [1, 1, 1, 2, 2, 3]

위 줄이 nums이고, 아래 줄이 버킷입니다. 버킷 아래 숫자가 버킷 번호이자 빈도입니다. 파랗게 칠한 1이 nums에 세 칸 있어서, 버킷 줄에서는 3번 버킷에 들어가 있습니다.

버킷은 값을 번호대로 나눠 담는 칸이고, 이렇게 버킷에 나눠 담아 순서를 얻는 방법을 버킷 정렬(bucket sort)이라고 합니다. 버킷 번호가 이미 빈도 순서라서, 번호가 큰 버킷부터 거꾸로 보며 값을 꺼내면 많이 나온 값부터 나옵니다. 꺼낸 값이 k개가 되면 멈춥니다.

정렬 풀이와 달라진 점은 값을 버킷에 넣을 때 다른 값과 한 번도 비교하지 않는다는 것입니다. 들어갈 버킷은 그 값의 횟수만 보고 바로 정해집니다. 하는 일은 nums를 한 번 세고, 값마다 한 번 버킷에 넣고, 버킷 n + 1개를 한 번 훑는 것까지라 전체가 O(n)입니다. n이 100,000이고 값이 모두 다르면 정렬은 비교를 백만 번 넘게 하지만(n log₂ n ≈ 170만), 버킷 풀이는 버킷 100,001개를 한 번씩 보는 것으로 끝납니다.

버킷 번호로 빈도 대신 값 자체를 쓰면 계수 정렬(counting sort)이 됩니다. 0~100점 시험 점수라면 101칸짜리 배열에 점수마다 사람 수를 세어 두고 0점 칸부터 읽으면 정렬된 순서가 나옵니다. 번호로 쓰는 수가 값인지 빈도인지만 다르고, 비교 대신 번호로 자리를 정한다는 원리는 같습니다.

직접 따라가 보기

아래에서 “다음”을 누르면 세기(2~7번째 단계), 버킷에 넣기(8~10번째), 거꾸로 꺼내기(11~13번째) 순서로 진행합니다. 변수 칸의 counts는 값마다 센 횟수이고, result는 버킷에서 꺼낸 값입니다. 11번째 단계에서 6, 5, 4번 버킷이 비어 있어 한 번에 지나가고, 13번째 단계에서 2번 버킷의 2까지 담으면 k = 2개가 차서 1번 버킷의 3은 보지 않고 끝납니다.

처음부터 이전 자동 재생 다음

단계 1 / 13

빈도별 버킷 · nums = [1, 1, 1, 2, 2, 3], k = 2

변수

counts

비어 있음

result

[]

nums를 왼쪽부터 한 칸씩 보며 값마다 몇 번 나왔는지 counts에 셉니다. "다음"을 눌러 보세요

• 지금 세는 칸 · 지금 보는 버킷
• 이번에 버킷에 넣는 값
• result에 담은 값
• 센 칸 · 지나간 버킷

대표 문제 풀이

제가 처음 풀었을 때는 횟수를 센 뒤 정렬했습니다. LeetCode에 제출해 채점받지는 않았고, 예제와 무작위 입력으로 결과만 확인한 코드입니다.

function answer(nums, k) {
  const numMap = new Map();
  nums.map(num => {
    numMap.set(num, numMap.has(num) ? numMap.get(num) + 1 : 1);
  });

  const arr = [];
  numMap.forEach((value, key) => {
    arr.push([key, value]);
  });
  arr.sort((a, b) => b[1] - a[1]);
  return arr.slice(0, k).map(data => data[0]);
}

답은 맞지만 arr.sort에서 O(m log m)이 들어 추가 조건을 맞추지 못합니다. 아래는 코치가 보여 준 버킷 풀이로, 정렬 한 줄을 버킷에 넣고 거꾸로 꺼내는 두 단계로 바꿨습니다. 주석의 번호는 위 시각화의 세기(①), 버킷에 넣기(②), 거꾸로 꺼내기(③)와 같습니다.

var topKFrequent = function (nums, k) {
  // ① 값마다 몇 번 나왔는지 센다
  const counts = new Map();
  for (const num of nums) {
    counts.set(num, (counts.get(num) ?? 0) + 1);
  }

  // ② 빈도를 버킷 번호로 써서 넣는다. 빈도는 1 이상 nums.length 이하다
  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [num, count] of counts) {
    buckets[count].push(num);
  }

  // ③ 번호가 큰 버킷부터 거꾸로 꺼내 k개를 채운다
  const result = [];
  for (let count = buckets.length - 1; count >= 1 && result.length < k; count--) {
    for (const num of buckets[count]) {
      result.push(num);
      if (result.length === k) break;
    }
  }
  return result;
};

buckets의 길이를 nums.length + 1로 잡는 이유는 모든 원소가 같은 값일 때 그 값이 nums.length번 버킷에 들어가야 하기 때문입니다. 버킷은 Array.from에 함수를 넘겨 칸마다 새 배열로 만듭니다. new Array(n + 1).fill([])로 만들면 모든 칸이 같은 배열 하나를 가리켜, 한 버킷에 넣은 값이 모든 버킷에 보입니다.

nums를 한 번 세고, 서로 다른 값마다 한 번 버킷에 넣고, 버킷을 한 번 훑으므로 시간은 O(n)입니다. counts와 buckets가 각각 최대 n개 남짓을 담으므로 공간도 O(n)입니다.

자주 하는 실수

정렬을 한 번 훑는 것으로 셉니다. 저는 정렬 풀이의 복잡도를 설명하면서 “배열을 전체 순회하며 저장할 때 1번, 횟수가 저장된 값을 정렬해 더 많이 등장한 원소를 구하는 데 1번 순회”라고 세어 O(n)이라고 답했습니다. sort는 코드에서 한 줄이지만 값 m개를 비교해 줄 세우는 데 O(m log m)이 듭니다. 줄마다 비용을 따로 적은 뒤 더하면 O(n + m log m)이 나오고, 추가 조건을 맞추려면 정렬 대신 버킷이 필요하다는 것도 이 계산에서 드러납니다.

Map에 없는 키에 1을 더하면 에러가 난다고 생각합니다. 처음 세는 값은 counts.get(num)이 undefined입니다. 저는 여기서 에러가 난다고 답했는데, JavaScript는 undefined + 1을 에러 없이 NaN으로 계산하고 그 뒤로 NaN + 1도 NaN이라, 그 값의 횟수가 조용히 NaN으로 남습니다. 버킷 풀이에서 ?? 0으로 기본값을 주는 이유가 이것입니다.