크기가 N인 정수 배열과 키 K가 주어졌을 때, 배열에서 등장 빈도가 가장 높은 상위 K개의 요소를 찾아 출력하는 것이 이번 문제의 목표입니다. 아래 예시를 통해 문제를 살펴보겠습니다.
문제 예시
예시 1
입력
N = 6
K = 2
arr[ ] = {1, 1, 1, 2, 2, 3}
출력
1 2
설명: 주어진 배열에서 빈도수가 가장 높은 상위 K=2개의 요소는 {1, 2}입니다. 1은 세 번, 2는 두 번 등장합니다.
예시 2
입력
N = 2
K = 1
arr[ ] = {1, 2}
출력
1
설명: 모든 요소의 빈도가 같을 경우, 조건을 만족하는 요소 중 하나인 {1}을 상위 K=1개 결과로 반환합니다.
문제 해결 접근 방법
핵심 아이디어는 간단합니다. 각 숫자가 몇 번 등장했는지 먼저 세고, 빈도수를 기준으로 내림차순 정렬한 뒤 앞에서부터 K개를 선택하면 됩니다. 이를 위해 해시맵(hashmap)을 사용합니다. 해시맵의 키(key)에는 배열의 현재 요소를 저장하고, 값(value)에는 해당 숫자의 등장 횟수를 저장합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- 배열의 크기 N과 N개의 정수로 이루어진 배열을 입력받습니다.
- 배열과 키 K를 매개변수로 받아 상위 K개의 최빈 요소를 반환하는 topKfrequent() 함수를 정의합니다.
- 배열을 한 번 순회하며 각 요소와 그 등장 횟수를 해시맵에 키-값 쌍으로 저장합니다.
- 해시맵의 데이터를 벡터(vector)로 옮긴 뒤, 빈도수를 기준으로 내림차순 정렬합니다.
- 빈도수 기준 정렬을 위해 pair의 second 멤버를 비교하는 bool 타입 헬퍼(compare) 함수를 사용합니다.
- 정렬된 벡터를 처음부터 순회하며 상위 K개의 최빈 요소를 출력합니다.
C++ 구현 코드
#include<bits/stdc++.h>
using namespace std;
bool compare(pair<int,int>& a, pair<int,int>& b){
return a.second > b.second;
}
void topKfrequent(int arr[], int n, int k){
unordered_map<int,int> mp;
for(int i = 0; i < n; i++){
mp[arr[i]]++;
}
vector<pair<int,int>> v(mp.begin(), mp.end());
sort(v.begin(), v.end(), compare);
for(int i = 0; i < k; i++){
cout << v[i].first << " ";
}
}
int main(){
int N = 5;
int arr[N] = {1, 1, 3, 2, 2};
int k = 2;
topKfrequent(arr, N, k);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
1 2
주어진 배열 {1, 1, 3, 2, 2}에서 1과 2는 각각 두 번씩 등장하여 최빈도를 기록하고, 3은 한 번만 등장합니다. 따라서 상위 K=2개의 최빈 요소는 1과 2입니다. 참고로 빈도수가 같은 요소 사이의 출력 순서는 unordered_map의 내부 해시 순서에 따라 달라질 수 있습니다.
시간 복잡도 분석
해시맵을 채우는 데 O(N), 정렬에 O(M log M)(M은 서로 다른 요소의 개수)이 소요되므로 전체 시간 복잡도는 O(N + M log M), 최악의 경우 O(N log N)입니다. 공간 복잡도는 해시맵에 요소별 빈도를 저장하므로 O(M)입니다. K가 N보다 훨씬 작은 경우에는 크기 K의 최소 힙(min-heap)을 사용하여 시간 복잡도를 O(N log K)까지 줄일 수 있습니다.