LeetCode

LeetCode 347 Top K Frequent Elements 풀이: 빈도 버킷 정렬

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

원소별 등장 횟수를 집계한 뒤 빈도가 높은 순서로 상위 k개를 골라야 한다. 단순 정렬은 가능하지만 문제의 후속 조건인 O(n log n)보다 빠른 알고리즘을 만족하려면 빈도 범위가 배열 길이 이하라는 점을 이용해야 하므로 Level 3으로 판단했다.

1. 문제 요약

정수 배열 nums에서 가장 자주 등장하는 원소 k개를 반환해야 한다. 결과의 순서는 상관없으며, 정답에 포함될 원소 집합은 유일하다고 보장된다.

입력 제한은 다음과 같다.

  • 1 <= len(nums) <= 10^5
  • -10^4 <= nums[i] <= 10^4
  • 1 <= k <= nums의 서로 다른 원소 개수

nums = [1, 1, 1, 2, 2, 3], k = 2라면 빈도가 3회인 1과 2회인 2를 반환한다. 반환 순서는 [1, 2]나 [2, 1] 모두 가능하다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

빈도 버킷 정렬

먼저 해시 맵 counts에 원소별 등장 횟수를 저장한다. 원소 하나의 최대 빈도는 len(nums)이므로, 인덱스를 빈도로 사용하는 버킷을 만들 수 있다.

buckets[f] = f번 등장한 원소들의 목록

빈도가 1인 원소는 buckets[1]에, 배열 전체와 같은 횟수로 등장한 원소는 buckets[len(nums)]에 넣는다. 이후 가장 높은 빈도 버킷부터 1까지 내려오며 원소를 꺼내 k개가 되면 즉시 반환한다.

빈도를 버킷 위치로 바꿔 상위 k개 찾기

빈도는 원소의 값 범위와 관계없이 1부터 n 사이에 있다. 빈도별로 원소를 묶으면 원소들을 빈도 기준으로 다시 정렬하지 않고도 높은 빈도부터 순회할 수 있다. 이때 버킷의 개수는 빈도 n을 포함해야 하므로 n + 1개를 만들어야 한다.

상태 전이와 경계 처리

처리 순서는 다음과 같다.

  1. counts에서 각 원소가 몇 번 등장했는지 센다.
  2. 각 (원소, 빈도)를 buckets[빈도]에 넣는다.
  3. buckets[n]부터 buckets[1]까지 역순으로 확인한다.
  4. 원소를 결과에 추가하고 결과 길이가 k가 되면 반환한다.

원소가 배열 전체에서 한 번만 등장하면 빈도 1 버킷에 들어간다. 반대로 하나의 원소가 모든 위치를 차지하면 빈도 n 버킷에 들어가므로 배열 크기보다 하나 더 큰 버킷 배열이 필요하다.

오답 접근과 반례

빈도 사전을 만든 뒤 모든 고유 원소를 빈도 내림차순으로 정렬하면 구현은 쉽지만, 고유 원소 수가 n에 가까울 때 O(n log n) 시간이 필요하다. 문제의 후속 조건인 O(n log n)보다 빠른 알고리즘을 만족하지 못한다.

최소 힙을 크기 k로 유지하는 방식은 O(n log k) 시간으로 개선할 수 있지만, 이 문제는 빈도가 배열 길이 이하로 제한되어 있으므로 버킷 정렬로 O(n)까지 줄일 수 있다.

버킷을 n개만 만들면 다음 반례에서 오류가 발생한다.

nums = [7, 7, 7], k = 1

7의 빈도는 3이므로 buckets[3]이 필요하다. 인덱스 0부터 n-1까지만 만들면 마지막 빈도 버킷을 저장할 수 없다.

시간·공간 복잡도

빈도 계산, 버킷에 원소 배치, 버킷 역순 순회는 모두 입력 크기에 비례한다. 시간 복잡도는 O(n)이다. 빈도 사전과 n + 1개 버킷을 사용하므로 공간 복잡도는 O(n)이다.

3. 문제 해결 코드 (Python)

class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = {}
        for num in nums:
            counts[num] = counts.get(num, 0) + 1

        buckets = [[] for _ in range(len(nums) + 1)]
        for num, frequency in counts.items():
            buckets[frequency].append(num)

        answer = []
        for frequency in range(len(nums), 0, -1):
            for num in buckets[frequency]:
                answer.append(num)
                if len(answer) == k:
                    return answer

        return answer

buckets[frequency]에 같은 빈도를 가진 원소가 여러 개 들어갈 수 있다. 문제는 결과 순서를 제한하지 않고 정답 원소 집합이 유일하므로, 같은 버킷 안의 순서는 별도로 정렬하지 않아도 된다.

반복문은 가장 높은 빈도부터 내려오며, 필요한 k개를 모으는 순간 종료한다. 마지막 return answer는 입력 조건상 반드시 앞에서 반환되지만, 함수의 반환 형식을 명확히 하기 위해 남겨 둔다.

복사해 실행할 테스트

빈도 동률에서는 반환 순서가 달라도 정답 집합은 같으므로 결과를 정렬해 검사한다.

solver = Solution()
assert set(solver.topKFrequent([1, 1, 1, 2, 2, 3], 2)) == {1, 2}
assert solver.topKFrequent([1], 1) == [1]

4. 공식 예제와 추가 검증

공식 예제와 단일 원소, 음수, 모든 원소가 서로 다른 경우를 Python 코드로 실행했다. 결과 순서가 자유로운 문제이므로 각 실행 결과의 집합과 길이를 기대값과 비교했다.

공식 예제

입력: nums = [1, 1, 1, 2, 2, 3], k = 2
기대 출력 집합: {1, 2}
확인 결과: 통과
검증 목적: 빈도 3회와 2회인 상위 원소 선택 확인

추가 검증 1: 원소 하나

입력: nums = [1], k = 1
기대 출력 집합: {1}
확인 결과: 통과
검증 목적: 최소 입력과 최대 빈도 버킷 1 처리 확인

추가 검증 2: 음수와 빈도 차이

입력: nums = [-1, -1, 2, 2, 2], k = 1
기대 출력 집합: {2}
확인 결과: 통과
검증 목적: 음수 원소를 포함한 빈도 집계와 최댓값 빈도 선택 확인

추가 검증 3: k가 서로 다른 원소의 개수와 같은 경우

입력: nums = [4, 4, 5, 5, 6, 6], k = 3
기대 출력 집합: {4, 5, 6}
확인 결과: 통과
검증 목적: 모든 빈도 버킷을 수집해 k개를 채우는지 확인

5. 다른 풀이 방식 검색 및 비교

모든 고유 원소를 정렬하는 방식은 O(n log n)이고, 최소 힙 크기를 k로 제한하는 방식은 O(n log k)다. 이 글의 버킷 방식은 빈도가 n 이하라는 문제 조건을 활용해 정렬 비용을 없애고 O(n) 시간에 결과를 수집한다. 대신 빈도 버킷 배열에 O(n) 공간을 사용한다는 차이가 있다.

마무리

Top K Frequent Elements는 빈도를 단순히 정렬하는 대신, 빈도 범위가 배열 길이로 제한된다는 점을 이용하는 문제다. 해시로 빈도를 세고 해당 빈도를 버킷의 인덱스로 사용하면 가장 높은 빈도부터 내려오며 필요한 원소만 모을 수 있다. 결과 순서가 자유롭기 때문에 같은 빈도 버킷 내부의 추가 정렬도 필요하지 않다.

#해시#LeetCode#난이도 3