문제 개요
비어 있지 않은 단어 목록이 주어졌을 때, 가장 많이 등장하는 상위 k개의 단어를 찾아야 합니다. 결과는 빈도수가 높은 순서부터 낮은 순서대로 정렬해야 하며, 두 단어의 빈도수가 같다면 알파벳 순서상 앞에 오는 단어를 먼저 배치합니다.
예를 들어 입력 배열이 ['the', 'sky', 'is', 'blue', 'the', 'weather', 'is', 'comfortable']이고 k가 3이라면 결과는 ["is", "the", "blue"]입니다. 'the'와 'is'는 각각 2번 등장해 최상위 두 자리를 차지하고, 나머지 단어들은 모두 1번씩 등장했으므로 그중 알파벳 순서가 가장 앞선 'blue'가 세 번째로 선택됩니다.
해결 접근 방법
이 문제는 맵(map)과 우선순위 큐(priority queue)를 조합하면 효율적으로 해결할 수 있습니다. 먼저 맵으로 단어별 등장 횟수를 집계한 뒤, 우선순위 큐를 이용해 상위 k개 후보만 계속 유지하는 방식입니다. 구체적인 단계는 다음과 같습니다.
- 맵 정의: 단어별 빈도수를 저장할 맵 m을 정의합니다.
- 우선순위 큐 생성: 상위 k개 후보를 관리할 우선순위 큐 v를 생성합니다.
- 빈도수 집계: i를 0부터 n(단어 배열의 크기)까지 반복하면서 m[words[i]] 값을 1씩 증가시킵니다.
- 큐 채우기: 맵의 각 요소 e에 대해 아래 규칙을 적용합니다.
- v의 크기가 k보다 작으면 e를 v에 삽입합니다.
- v.top()의 빈도값이 e의 빈도값보다 작으면, v의 최상단 요소를 제거한 뒤 e를 삽입합니다.
- v.top()의 빈도값이 e의 빈도값과 같고 v.top()의 키(단어)가 e의 키보다 사전순으로 뒤라면, 최상단 요소를 제거하고 e를 삽입합니다.
- 결과 추출 준비: 결과를 담을 문자열 배열 res를 정의합니다.
- v가 빌 때까지 다음을 반복합니다.
- temp에 v의 최상단 요소를 저장합니다.
- v에서 최상단 요소를 제거합니다.
- temp의 키(단어)를 res 배열에 추가합니다.
- 정렬 후 반환: res 배열을 뒤집어 올바른 순서로 만든 뒤 반환합니다.
예제(C++)
더 나은 이해를 돕기 위해 다음 구현 예제를 살펴보겠습니다.
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
struct Comparator{
bool operator()(pair <string ,int> a, pair <string, int> b){
if(a.second != b.second) return !(a.second < b.second);
return !(a.first > b.first);
}
};
class Solution {
public:
static bool cmp(pair <string, int> a, pair <string, int> b){
if(a.second != b.second) return a.second > b.second;;
return a.first < b.first;
}
vector<string> topKFrequent(vector<string>& words, int k) {
map<string, int> m;
priority_queue < pair <string, int>, vector < pair <string, int> >, Comparator > v;
for(int i = 0; i < words.size(); i++){
m[words[i]]++;
}
map<string, int> :: iterator i = m.begin();
while(i != m.end()){
if(v.size() < k){
v.push(*i);
}
else if(v.top().second < i->second){
v.pop();
v.push(*i);
}
else if(v.top().second == i->second && v.top().first > i->first){
v.pop();
v.push(*i);
}
i++;
}
vector <string> res;
while(!v.empty()){
pair <string, int> temp = v.top();
v.pop();
res.push_back(temp.first);
}
reverse(res.begin(), res.end());
return res;
}
};
main(){
Solution ob;
vector<string> v = {"the", "sky", "is", "blue", "the", "weather", "is", "comfortable"};
print_vector(ob.topKFrequent(v, 3));
}코드 설명
Comparator 구조체는 우선순위 큐의 정렬 기준을 정의합니다. 두 단어의 빈도수가 다르면 빈도가 높은 쪽이 우선순위를 갖고, 빈도수가 같다면 알파벳 순서상 앞선 단어가 우선순위를 갖습니다. 그 결과 큐의 최상단에는 항상 교체 대상이 되는 요소, 즉 빈도가 가장 낮거나 같은 빈도 중 사전순으로 가장 뒤인 단어가 위치하게 됩니다.
모든 단어를 처리한 뒤에는 큐에서 요소를 하나씩 꺼내 res에 담습니다. 이때는 빈도가 낮은 순서로 쌓이므로 마지막에 reverse()를 호출해 빈도 내림차순의 최종 결과를 완성합니다. 시간 복잡도는 맵 집계에 O(n log n), 우선순위 큐 연산에는 고유 단어 수를 u라 할 때 O(u log k)가 소요됩니다.
입력
["the", "sky", "is", "blue", "the", "weather", "is", "comfortable"] 3
출력
["is","the","blue"]