베스트앨범

문제

문제의 시간복잡도

문제에서의 n의 갯수는 10000개로 $O(n)$안에 문제를 풀어야 겠다는 생각을 했다. 그리고 여기서 n의 수가 genre의 수로 divide가 되기 때문에 어쩌면 $O(nlogN)$의 시간에서도 동작하지 않을까 라고 생각을 했다.

문제의 파악

먼저 주어진 변수는 genres와 plays가 있었다.
여기서 genres는 모든 곡의 집합으로 곡의 장르와 고유번호를 알려준다.
plays는 곡의 고유번호와 해당 곡의 재생횟수의 집합이다.

이 문제에서 중요했던 점은 제한사항이 많았다는 점이다.
그래서 문제를 풀 때 이 부분을 잘 정리하고 하나하나씩 클리어 하느식으로 했다면 오류를 잡는데 시간을 줄일 수 있었을 것 같다는 생각을 했다.

풀이

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

using namespace std;

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

bool compare2(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;
    unordered_map<string,int> genre; 
    unordered_map<string,vector<pair<int,int>>> in_genre; 
    
    for(int i=0;i<genres.size();i++)
    {
        if(genre.end() == genre.find(genres[i]))
        {
            genre.insert(make_pair(genres[i],plays[i]));
            pair<int,int> p = make_pair(i,plays[i]);
            vector<pair<int, int>> tmp;
            tmp.push_back(p);
            in_genre.insert(make_pair(genres[i],tmp));
        }
        else
        {
            genre[genres[i]] += plays[i];
            in_genre[genres[i]].push_back(make_pair(i,plays[i]));
        }
    }
    
    vector<pair<string, int>> vec_genre(genre.begin(), genre.end());
    
    sort(vec_genre.begin(),vec_genre.end(),compare2);
    
    for(int i=0; i<vec_genre.size();i++)
    {
        string s = vec_genre[i].first;
        vector<pair<int,int>> v = in_genre[s];
        sort(v.begin(),v.end(),compare);
        answer.push_back(v[0].first);
        if(v.size() > 1) answer.push_back(v[1].first);
    }
    return answer;
}

hash테이블을 사용하는 방법을 제대로 배운 문제였던 것 같다.

사실 문제에 대한 접근은 1차원적으로 가능했다.
아이디어를 짜는데는 10분도 채 걸리지 않은 것 같았다.

하지만 pair, sort, unordered_map을 사용함에 있어서 미숙함 점들이 많았던 점이 문제를 푸는데 오래 걸리게 한 요소였던 것 같다.

가장 크게 내 발목을 잡아서 풀이까지 보게 한 범인은
장르의 해당하는 곡이 하나인 경우에 대한 예외처리였다.

그냥 이것에 대해서 for문을 두번 돌아서 앞에 두개만을 찾으면 된다라고 생각을 했는데, 결과는 그렇지 못하였다. 계속해서 50점이 나와서 보고보고 봐도 논리적으로 틀린점을 찾지 못해 고군분투하였다.

vector의 요소가 없으면 쓰레기 값을 리턴하는 것을 명심하자..