[프로그래머스 > 고득점kit 해시] 베스트 앨범 (C++)

 

 

 

programmers.co.kr/learn/courses/30/lessons/42579

코딩테스트 연습 - 베스트앨범

 

 

level 3 답게 다른 해시 문제보다 정말 요구사항이 많은 문제였다!

 

문제를 정확하게 이해하고, 알고리즘을 어떻게 짤지 잘 계획하지 않고 무작정 손부터 움직이면 안되는 문제였다.

 

 

 

먼저 문제를 천천히 뜯어보자.

 

장르 별로 가장 많이 재생된 노래 2곡씩 모아 베스트 앨범을 출시하려고 한다.

노래는 각 고유번호가 있으며, 노래 수록 기준은 다음과 같다.

 

(1) 가장 많이 재생된 장르가 우선 순위를 갖는다

(2) 장르 내 가장 많이 재생된 노래가 우선 순위를 갖는다

(3) 재생 횟수가 같다면, 고유번호가 낮은 쪽이 우선 순위를 갖는다

 

즉, 장르>노래 재생횟수>낮은 고유번호  순으로 우선 순위를 갖는다

 

이 때 예외 사항으로, 장르에 속한 곡은 최소 1개로, 2곡 미만인 경우 그냥 1곡만 싣는 예외처리가 필요하다.

덧붙여 모든 장르의 재생 횟수는 다르므로, 재생 횟수가 같을 경우의 예외 처리는 고려하지 않아도 된다.

 

 

 

 

 

그럼 문제에 대한 아이디어를 생각해보자.

 

 

크게 두 단계의 정렬을 실행해야 하는데

 

(1) 재생 횟수가 큰 순서로 장르 정렬

 

(2) 재생 횟수가 큰 순서로 장르 내 곡 정렬

 

이  필요하다. 각 단계 별로 알고리즘을 생각해보도록 하자.

 

 

 

[단계1] 재생 횟수가 큰 순서로 장르 정렬

 

 

 

 

[단계2] 재생 횟수가 큰 순서로 장르 내 곡 정렬

 

 

 

위와 같은 단계로 나누어 코드를 짤 수 있겠다.

 

 

본격적으로 main 코드를 짜기 전에, 단계1과 단계2에서 사용될 sort 함수의 인자 compare 함수를 정의해주어야 한다.

 

코드는 아래와 같다.

 

 

 

 

 

 

 

[단계 1] 장르의 재생횟수 내림차순 정렬

bool comp_genre(pair<string,int> a, pair<string,int> b) //장르의 총 재생횟수 순으로 정렬해줄 비교함수
{
    return a.second>b.second;
}

 

 

 

 

[단계 2] 곡의 재생횟수 내림차순 정렬 및 같을 경우 고유번호 오름차순 정렬

bool comp_song(pair<int,int> a, pair<int,int> b) // pair<고유번호,재생횟수> 배열을 정렬해줄 비교함수
{
    if(a.second == b.second)
    {
        return a.first < b.first;
    }
    return a.second > b.second;
}

 

 

 

 

 

main 코드 이전에 이렇게 두 compare함수를 정의해 주었다면, 단계 1과 단계 2에 해당하는 코드를 짜보자.

중요한 것은 내가 필요한 pair type으로 올바른 컨테이너를 선언해주는 것이다.

 

 

 

[단계 1]

 

 vector<pair<string,int>> v_genres; //재생횟수와 장르를 담을 vector와 map
    unordered_map<string,int> maps; 
    
    int song_num = genres.size();
    
    for(int i=0; i<song_num; i++)
    {
        maps[genres[i]] += plays[i];
    }
    
    for(pair<string,int> atom : maps)
    {
        v_genres.push_back(make_pair(atom.first, atom.second));
        //맵을 벡터로 옮겨준다.
    }
    
    sort(v_genres.begin(), v_genres.end(), comp_genre);
    //재생이 많이 된 장르 순서대로 정렬
    

 

 

 

 

[단계 2] 

 

pair<int,int> temp[10002];
    for(pair<string,int> atom : v_genres)
    {
        string target_genre = atom.first; //타겟 장르
        int cnt=0; //장르 내 음악 개수
        int it=0; //iterator
        
        for(int i=0; i<song_num; i++) 
        {
            
            if(genres[i] == target_genre)//해당 장르 내 음악과 고유번호 골라내기
            {
                cnt++;
                temp[it] = make_pair(i,plays[i]); //고유번호, 재생횟수 한쌍
                it++;
            }
            
        }
        
        sort(temp,temp+cnt,comp_song);
        answer.push_back(temp[0].first);
        if(cnt!=1)
        {
            answer.push_back(temp[1].first);
        }
        
    }
    
    return answer;

 

 

 

 

 

 

 

앞서 미리 설계한 두 단계에 맞춰 코드를 위와 같이 짜주면 정답화면을 볼 수 있다!

다른 사람들의 정답 코드를 살펴보니 내가 짠 알고리즘과 같아 신기하고 반가웠다ㅎㅎ

풀다가 그냥 솔루션을 찾고 싶은 마음이 굴뚝같았는데, 포기하지 않고 끝까지 내 방식대로 풀어내는 인내심이 정말 중요하다고 다시 한 번 느꼈다.

 

 

 

 

 

전체 코드는 아래와 같다.

 

 

#include <string>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

bool comp_song(pair<int,int> a, pair<int,int> b) // pair<고유번호,재생횟수> 배열을 정렬해줄 비교함수
{
    if(a.second == b.second)
    {
        return a.first < b.first;
    }
    return a.second > b.second;
}

bool comp_genre(pair<string,int> a, pair<string,int> b) //장르의 총 재생횟수 순으로 정렬해줄 비교함수
{
    return a.second>b.second;
}





vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    
    vector<pair<string,int>> v_genres; //재생횟수와 장르를 담을 vector와 map
    unordered_map<string,int> maps; 
    
    int song_num = genres.size();
    
    for(int i=0; i<song_num; i++)
    {
        maps[genres[i]] += plays[i];
    }
    
    for(pair<string,int> atom : maps)
    {
        v_genres.push_back(make_pair(atom.first, atom.second));
        //맵을 벡터로 옮겨준다.
    }
    
    sort(v_genres.begin(), v_genres.end(), comp_genre);
    //재생이 많이 된 장르 순서대로 정렬
    

    pair<int,int> temp[10002];
    for(pair<string,int> atom : v_genres)
    {
        string target_genre = atom.first; //타겟 장르
        int cnt=0; //장르 내 음악 개수
        int it=0; //iterator
        
        for(int i=0; i<song_num; i++) 
        {
            
            if(genres[i] == target_genre)//해당 장르 내 음악과 고유번호 골라내기
            {
                cnt++;
                temp[it] = make_pair(i,plays[i]); //고유번호, 재생횟수 한쌍
                it++;
            }
            
        }
        
        sort(temp,temp+cnt,comp_song);
        answer.push_back(temp[0].first);
        if(cnt!=1)
        {
            answer.push_back(temp[1].first);
        }
        
    }
    
    return answer;
}