문제 소개
TV 프로그램 목록과 각 프로그램별 시청 시간 목록, 그리고 정수 k가 주어진다고 가정해 봅시다. shows[i]와 duration[i]는 각각 i번째 시청자가 본 프로그램 이름과 시청 시간을 나타냅니다. 이때 가장 많이 시청된 상위 k개 프로그램의 총 시청 시간을 구하는 것이 우리의 과제입니다.
예를 들어, 입력이 다음과 같다고 해보겠습니다.
- shows: ["Castle Play", "Fairy Tale Series", "Castle Play", "Jerry Mouse", "Rich Boy"]
- duration: [6, 4, 6, 14, 5]
- k = 2
이 경우 출력은 26이 됩니다. "Castle Play"는 두 번 등장하여 총 12분, "Jerry Mouse"는 14분으로 상위 2개 프로그램의 합계가 26이 되기 때문입니다.
해결 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 프로그램 이름을 키로, 누적 시청 시간을 값으로 저장할 맵(map) m을 정의합니다.
- 배열 v의 크기를 n에 저장합니다.
- i가 0부터 n 미만일 때까지 반복하면서 m[v[i]]에 d[i]를 더해 각 프로그램의 시청 시간을 누적합니다.
- 정수 배열 arr를 정의하고, 맵 m의 모든 키-값 쌍을 순회하며 값을 arr 끝에 추가합니다.
- arr를 내림차순으로 정렬합니다.
- 결과값 ret을 0으로 초기화한 뒤, i가 0부터 k 미만일 때까지 반복하며 ret에 arr[i]를 더합니다.
- ret을 반환합니다.
C++ 구현 예제
아래 코드를 통해 실제 구현을 확인해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<string>& v, vector<int>& d, int k) {
map <string, int> m;
int n = v.size();
for(int i = 0; i < n; i++){
m[v[i]] += d[i];
}
vector < int > arr;
for(auto it : m){
arr.push_back(it.second);
}
sort(arr.rbegin(), arr.rend());
int ret = 0;
for(int i = 0; i < k; i++){
ret += arr[i];
}
return ret;
}
};
int main(){
vector<string> v = {"Castle Play", "Fairy Tale Series", "Castle Play", "Jerry Mouse", "Rich Boy"};
vector<int> v1 = {6, 4, 6, 14, 5};
Solution ob;
cout << (ob.solve(v, v1, 2));
}입력
{"Castle Play", "Fairy Tale Series", "Castle Play", "Jerry Mouse", "Rich Boy"}, {6, 4, 6, 14, 5}, 2출력
26
코드 설명
이 알고리즘의 핵심은 맵을 활용해 동일한 프로그램의 시청 시간을 효율적으로 집계하는 것입니다. 맵 연산에는 O(log n)의 시간이 걸리고, 이후 정렬에 O(m log m)(m은 고유 프로그램 수)의 시간이 소요됩니다. 전체적인 시간 복잡도는 O(n log n)으로 매우 효율적입니다. 마지막으로 내림차순 정렬된 배열에서 상위 k개의 값만 더하면 원하는 답을 얻을 수 있습니다.