하루 하루는 성실하게
인생 전체는 되는대로

[프로그래머스] 베스트앨범

1 minute read

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

  1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
  2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
  3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. 노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한 사항

  • genres[i]는 고유번호가 i인 노래의 장르입니다.
  • plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
  • genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
  • 장르 종류는 100개 미만입니다.
  • 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
  • 모든 장르는 재생된 횟수가 다릅니다.

풀이

{장르 : 총 재생횟수}를 저장하는 해시맵과 {장르 : 해당 장르에 속하는 (노래 번호, 재생횟수) 집합}을 저장하는 해시맵을 선언하여 한 번의 탐색으로 저장을 완료한다. 그리고 총 재생 횟수에 따라서 장르를 정렬하고, 그 순서대로 노래를 정렬하여 문제를 해결했다.문제를 풀면서도, 조금 더 깔끔하게 푸는 방법은 없나? 하는 생각이 계속해서 들었다. 결과적으로는 한 번의 제출로 바로 통과되었고, 통과 이후 다른 사람들의 코드를 보더라도 ‘우와’할 정도로 깔끔한 코드는 발견하지 못 했다. 자신감이 부족한 탓인지 자꾸 스스로에 대한 의심이 드는 것 같은데, 문제를 더 많이 풀어서 경험을 쌓아놓으면 해결될 것 같다.

코드

#include <string>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

bool cmp(pair<string,int> a , pair<string,int> b){
    return a.second > b.second;
}

bool cmp_song(pair<int,int> a , pair<int,int> b){
    if(a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> ans;
    
    map<string, vector<pair<int,int>>> m;
    map<string, int> cnt;
    for(int i =0;i < genres.size(); ++i){
        m[genres[i]].push_back(make_pair(i,plays[i]));
        cnt[genres[i]] += plays[i];
    }
    
    vector<pair<string,int>> v(cnt.begin(),cnt.end());
    sort(v.begin(), v.end(), cmp);
    
    string genr;
    for(pair<string,int> item : v){
        genr = item.first;
        sort(m[genr].begin(), m[genr].end(), cmp_song);
        ans.push_back(m[genr][0].first);
        if(m[genr].size() > 1) ans.push_back(m[genr][1].first);
    }
    
    return ans;
}

우선순위 큐 sort

vector를 sort하는 cmp함수를 작성하다가 문득 ‘priority_queue 비교함수는 어떻게 재정의했더라…?’하는 생각이 들었다. 지난해 코딩테스트를 연습하면서 수없이 많이 했었는데도 잘 생각이 나지 않았다. vector를 sort할 때는 비교 연산자의 대소를 정하는 것이 직관적(‘>’를 쓴다면 왼쪽이 더 큰 값을 가질 것)이라 헷갈릴 일이 없었는데, priority_queue는 트리 구조여서 그런지 매번 헷갈렸다.

struct cmp {
    bool operator()(int a, int b) {
        return a > b;
    }
};

priority_queue는 비교 연산자를 자신의 부모 노드와 비교하는데 사용하므로 a가 b보다 큰 것이 참이면 swap을 진행하게 되고, 결과적으로 queue의 top에는 가장 작은 값이 존재하게 된다. vector의 sort를 이해하는 방식으로 생각했을 때, 우선순위 큐의 경우에는 반대로 생각해야함을 알 수 있다.

You may also enjoy