프로그래머스 해시, 베스트 앨범

문제

https://programmers.co.kr/learn/courses/30/parts/12077

풀이방법

솔직히 말하면 해시라는 알고리즘 태그가 왜 존재하는지는 모르겠지만 그걸 신경쓰지 않고 푼다면, 각 장르에 대해 모든 재생 횟수를 구한 다음에 총 재생 횟수가 많은 순서대로 첫 번째로 정렬하고, 장르가 같은 경우에는 각자의 재생횟수로 두 번째로 정렬하는 방식으로 O(nlogn) (내가 직접 구현한다면 O(n^2), nlogn 시간내에 구현하기 힘듬...) 시간으로 풀었을 것 같다. 다만 이 경우에는 장르쪽 index가 좀 복잡하게 되었을 것 같긴 하다.

하지만 만약에 해시를 사용한다고 푼다면 c++에 구현되어 있는 unordered_map을 사용한다. (map도 사용안해봐서 차이는 잘모르겠지만 map은 정렬을 해주고 unordered_map은 정렬을 안해준다고 한다, map은 red-black tree이고 unordered_map은 hash이기 때문에) 이 unordered_map은 내부구조는 모르지만 string을 index로 사용할 수 있는 파이썬의 딕셔너리 같은 구조라고 현재는 생각하고 있다.

이를 이용해서 장르 이름을 index로해서 장르의 재생횟수를 저장하고 튜플을 통해 compare 함수를 정의하고 튜플을 벡터에 담아 c++ sort를 사용하면 아래와 같이 정답이 나오는 모습을 볼 수 있다.

실수

실수라고 하기에는 애매하지만 부족했던 점을 적었다. 워낙 명확했던 문제라서 생각하는데에는 어려움이 없었지만 구현에 오랜 시간이 걸렸다.

• STL을 사용할 줄 몰라서 인터넷에 검색을 많이 하면서 진행하였다. 코테에서는 이렇게 할 수 없으니 관련된 연습을 많이 해야한다.

• 프로그래머스같은 경우에는 solution 함수를 작성하기 때문에 IDE 사용이 귀찮거나 어렵다는 단점이 있었다. 코테 수준 문제에서는 IDE 없이도 문제를 작성할 수 있도록 연습해야 한다.

코드

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

using namespace std;

unordered_map<string, int> genres_hash; // 장르의 횟수를 저장한다.

bool compare(tuple<string, int, int>& front, tuple<string, int, int>& back){ // 비교 기준
    
    string front_genres, back_genres;
    
    front_genres = get<0>(front);
    back_genres = get<0>(back);
    
    int front_plays, back_plays;
        
    front_plays = get<1>(front);
    back_plays = get<1>(back);
    
    int front_index, back_index;
            
    front_index = get<2>(front);
    back_index = get<2>(back);
    
    if(genres_hash[front_genres] == genres_hash[back_genres]){ // 같은 경우에는 다음 우선순위 확인 아니라면 해당 결과에 따라 결정.
        
        if(front_plays == back_plays){
            
            return front_index < back_index;
            
        }
        
        return front_plays > back_plays;
        
    }
    
    return genres_hash[front_genres] > genres_hash[back_genres];
    
}

vector<int> solution(vector<string> genres, vector<int> plays){
    
    vector<int> answer;

    vector<tuple<string, int, int>> temp_vector;

    for(int i = 0; i < genres.size(); i++){ // 장르당 횟수를 구하면서 벡터에 값을 정리해서 넣음
        
        genres_hash[genres[i]] += plays[i];
        temp_vector.push_back(make_tuple(genres[i], plays[i], i));
        
    }

    sort(temp_vector.begin(), temp_vector.end(), compare); // 정렬
    
    unordered_map<string, int> genres_count;
    
    for(int i = 0; i < temp_vector.size(); i++){ // 장르당 뽑을 수 있는 곡의 수는 최대 2
        
        if(genres_count[get<0>(temp_vector[i])] != 2){
            
            answer.push_back(get<2>(temp_vector[i]));
            genres_count[get<0>(temp_vector[i])]++;
            
        }
        
    }
    

    return answer;
}