정수로 이루어진 비어 있지 않은 배열이 하나 주어졌다고 가정해 봅시다. 우리가 해야 할 일은 이 배열에서 가장 자주 등장하는 상위 k개의 요소를 반환하는 것입니다. 예를 들어 배열이 [1,1,1,1,2,2,3,3,3]이고 k = 2라면, 1은 네 번, 3은 세 번 등장하므로 결과는 [1, 3]이 됩니다.
문제 접근 방법
이 문제는 크게 두 단계로 나누어 생각할 수 있습니다. 첫째, 각 숫자가 몇 번 등장하는지 빈도를 계산합니다. 둘째, 빈도를 기준으로 내림차순 정렬하여 상위 k개를 추출합니다. 여기서는 별도의 정렬 함수 없이 빈도를 인덱스로 사용하는 버킷(bucket) 방식으로 효율적으로 해결할 수 있습니다.
구체적인 해결 절차는 다음과 같습니다.
number_frequency: 각 숫자의 등장 횟수를 저장할 빈 딕셔너리(맵)를 준비합니다.frequency_list: '빈도 → 해당 빈도로 등장하는 숫자 목록'을 저장할 빈 딕셔너리를 준비합니다.- 배열
nums의 각 요소i에 대해:i가number_frequency에 없다면number_frequency[i] = 1로 설정하고, 이미 있다면 값을 1 증가시킵니다.
number_frequency의 각 키-값 쌍에 대해:- 빈도 값이
frequency_list에 없다면frequency_list[value] = [key]로 새 리스트를 만들고, 이미 있다면 해당 리스트에 키를 추가합니다.
- 빈도 값이
- 결과를 담을 빈 리스트
result를 생성합니다. i를 배열 길이부터 1까지 감소시키면서 반복합니다:i가frequency_list에 존재하면, 해당 빈도를 가진 숫자들을result에 모두 추가합니다.result의 길이가 k 이상이 되면 반복을 중단합니다.
- 최종
result를 반환합니다.
이 방식은 배열의 최대 길이만큼만 탐색하면 되므로 전체 시간 복잡도는 O(n)입니다. 일반적인 정렬 기반 접근(O(n log n))보다 효율적이라는 장점이 있습니다.
구현 예제
아래 코드를 통해 실제 동작을 더 잘 이해할 수 있습니다.
class Solution(object):
def topKFrequent(self, nums, k):
number_frequency = {}
frequency_list = {}
# 1단계: 각 숫자의 등장 횟수 계산
for i in nums:
if i not in number_frequency:
number_frequency[i] = 1
else:
number_frequency[i] += 1
# 2단계: 빈도를 키로 하는 버킷 리스트 생성
for key, value in number_frequency.items():
if value not in frequency_list:
frequency_list[value] = [key]
else:
frequency_list[value].append(key)
# 3단계: 높은 빈도부터 상위 k개 수집
result = []
for i in range(len(nums), 0, -1):
if i in frequency_list:
result.extend(frequency_list[i])
if len(result) >= k:
break
return result
ob1 = Solution()
print(ob1.topKFrequent([1,1,1,1,2,2,3,3,3], 2))입력
[1,1,1,1,2,2,3,3,3] 2
출력
[1, 3]
동작 과정 살펴보기
위 입력값으로 코드가 실행되면 다음과 같이 진행됩니다.
- 1단계 후
number_frequency는{1: 4, 2: 2, 3: 3}이 됩니다. - 2단계 후
frequency_list는{4: [1], 2: [2], 3: [3]}이 됩니다. - 3단계에서 빈도 4 → 3 순서로 숫자를 수집하므로
[1, 3]이 반환되고, 길이가 k = 2에 도달했으므로 반복이 종료됩니다.
이처럼 해시 맵 두 개와 역방향 반복만으로 정렬 없이도 상위 k개의 빈번한 요소를 선형 시간에 구할 수 있습니다.