[C++] 프로그래머스 베스트 앨범 풀이(해시)

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

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

이 문제는 프로그래머스의 코딩테스트 연습 - 해시 - 베스트앨범이라는 문제이다.

위 링크를 타고 문제를 읽어보면 생각보다 단순하지 않게 느껴질 것이다.

우선 아래는 직접 풀은 코드이다.

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

using namespace std;

bool cmp(pair<int,int> a, pair<int,int> b) { //map에 있는 vector 정렬
    return a.second > b.second;
}

bool cmp2(pair<string,int> a, pair<string,int> b) { //vector정렬
    return a.second > b.second;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string,vector<pair<int,int>>> m;
    vector<pair<string,int>> v;
    for(int i = 0; i < genres.size(); i++) {
        if(m.find(genres[i]) == m.end()) { //처음 보는 장르인 경우
            vector<pair<int,int>> tmp; //벡터를 생성하여 번호와 재생 수를 저장
            tmp.push_back({i, plays[i]});
            m.insert({genres[i], tmp});
            v.push_back({genres[i], plays[i]}); //벡터에 추가
        }
        else { //이미 있는 장르인 경우
            m[genres[i]].push_back({i, plays[i]}); //map에 번호와 재생 수를 추가
            for(int j = 0; j < v.size(); j++) { //vector에서 같은 장르를 찾음
                if(genres[i] == v[j].first) {
                    v[j].second += plays[i]; //장르의 전체 재생 수 추가
                    break;
                }
            }
        }
    }
    sort(v.begin(), v.end(), cmp2); //장르별 전체 재생 수 정렬
    for(auto it = m.begin(); it != m.end(); it++) { //같은 장르의 각각 재생 수 정렬
        sort((*it).second.begin(),(*it).second.end(), cmp);
    }
    for(auto it = v.begin(); it != v.end(); it++) { //장르별 재생 수가 많은 순서대로 
        answer.push_back(m[(*it).first][0].first); //첫 번째 많은 재생 수 추가
        if(m[(*it).first].size() > 1) { //만약 재생 수가 2개 이상인 경우 추가
            answer.push_back(m[(*it).first][1].first);
        }
    }
    
    
    
    return answer;
}

이 문제는 map과 vector를 이용하여 풀었다.

우선 이 문제에서는 장르별 전체 곡 수를 저장할 vector와 각 장르에서의 곡 번호와 재생 수를 저장할 map을 선언하였다.

map에는 첫 번째 인자로 string을 주어 장르 이름을 통해 접근할 수 있게하고 두 번째 인자로 vector<pair<int,int>>를 주어 곡 번호와 재생 수를 저장할 수 있게한다.

주어진 입력을 모두 돌며 map과 vector에 저장한 다음 sort함수를 이용해 장르별 재생 수와 각 장르에서의 곡별 재생수를 내림차순으로 정렬한다.

그 다음 정렬된 vector를 처음부터 돌며 가장 많은 곡을 순서대로 answer에 넣는다. 이때 한 장르의 전체 곡 수가 1개일 수 있으므로 if문을 이용해 장르의 곡 수가 2개 이상인지 확인하고 추가한다.

이 문제를 풀며 코드도 깔끔하게 작성하지 못하였고 풀이 방식도 간결하지 못하다고 느꼈지만 효용성을 채점하는 부분이 없고 정확성 채점만 존재했기 때문에 vector, map을 모두 이용하여 푸는 방법 밖에 떠올리지 못했다.

이 문제에서 중요했던 스킬은 iterator를 사용하는 것과 vmap에서 type으로 또 다른 vector를 넣어 이를 이용하는 방식이 관건이었다. 직접 작성하면서도 헷갈리는 부분이 굉장히 많았고 풀이는 처음에 맞았지만 i와 j를 잘 못 쓰는 바람에 시간이 조금 더 걸렸었다. c++을 활용한 코딩테스트 문제를 풀 때 vector는 기본이고 set과 map을 활용해야하는 문제가 굉장히 많다고 느끼기 때문에 c++의 STL을 잘 활용할 수 있는 공부가 필요하다고 생각한다. 문제를 풀고 다른 사람들의 풀이를 보고 더 짧은 코드는 어떻게 돌아가는지 이해하는 것도 중요한 것 같다.