[Programmers Level3] 베스트 앨범(C++)

※주의※
저의 풀이가 정답은 아닙니다.
다른 코드가 더 효율적이거나 좋을 수 있습니다.
언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

[문제 풀이 사이트]

 

 

프로그래머스

 

 

[문제 설명]

 

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

 

1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
3. 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

 

[제한 사항]

 

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

 

[입출력 예]

 

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

 

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

 

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

 

• 장르 별로 가장 많이 재생된 노래를 최대 두 개까지 모아 베스트 앨범을 출시하므로 2번 노래는 수록되지 않습니다.

 

[입출력 예 설명]

 

 

generes	plays	return
["classic", "pop", "classic", "classic", "pop"]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]

 

 

[문제 풀이]

 

알고리즘보단 코드를 작성하면서 알게된 사실을 정리하려고 한다.

코드 내에 key 중복이 허용되는 multimap을 사용했는데 중복되는 key값이 여러개이기 때문에 find 함수로 찾기엔 어렵다.
그래서 중복되는 key 값을 찾아야할 때
map에서는 lower_bound와 upper_bound를 이용하여 찾고자 하는 key 값을 모두 찾을 수 있다.

예를 들어 중복된 key값을 저장할 수 있는 multimap이 아래와 같이 정의되어 있다고 하자.
multimap<string, int> multi;

정의 후 값을 pair형태로 insert 한다.
multi.insert(make_pair("pop", 50));
multi.insert(make_pair("classic", 170));
multi.insert(make_pair("pop", 150));
multi.insert(make_pair("pop", 200));

그리고 multimap에서 key 값이 "pop"인 요소를 모두 찾으려고 한다.
그렇다면 map은 lower_bound와 upper_bound를 지원하기 때문에 아래와 같이 쓸 수 있다.

multi.lower_bound("pop")
➜ lower_bound는 key값이 "pop"보다 크거나 같은 첫번째 요소의 반복자를 리턴한다.

multi.upper_bound("pop")
➜ upper_bound는 key값이 "pop"보다 큰 첫번째 요소의 반복자를 리턴한다.

그래서 아래와 같이 코드를 작성하면

for(auto iter = multi.lower_bound("pop"); iter != multi.upper_bound("pop"); iter++) {
	cout << iter->first << " " << iter->second << '\n';
}

key값이 "pop"인 모든 요소를 찾을 수 있다.

[최종 코드]

 

[GitHub]

 

 

GitHub - SmallPeanutPark/Programmers: Study Programmers for Coding Test

 

 

#include <string>
#include <vector>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
multimap<string, pair<int, int>> genresTime; // 각 장르 시간 따로 따로 저장 value의 first는 재생 시간, second는 고유 번호저장
map<string, int> totalgenresTime; // 같은 장르 시간 누적 저장
/*
속한 노래가 많이 재생된 장르를 먼저 수록합니다.
장르 내에서 많이 재생된 노래를 먼저 수록합니다.
장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
각 장르당 2개만
*/
void initialize(int len, vector<string> g, vector<int> p) {
    for(int i = 0; i < len; ++i) {
        string str = g[i];
        totalgenresTime[str] += p[i];
        genresTime.insert(make_pair(str, make_pair(p[i], i)));
    }
}

bool cmp(const pair<string, int> p1, const pair<string, int> p2) {
    return p1.second > p2.second;
}

vector<pair<string, int>> case1() {
    // 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
    // map to vector
    vector<pair<string, int>> temp;
    for(auto iter = totalgenresTime.begin(); iter != totalgenresTime.end(); ++iter) {
        temp.emplace_back(make_pair(iter->first, iter->second));
    }
    // 많이 재생된 장르 내림차순 정렬 : 큰 값이 앞에 옴
    sort(temp.begin(), temp.end(), cmp);
    return temp;
}

bool isFinalcmp(pair<int, int> p1, pair<int, int> p2) {
    int p1_first = p1.first;
    int p2_first = p2.first;
    if(p1_first == p2.first) {
        int p1_second = p1.second;
        int p2_second = p2.second;
        if(p1_second > p2_second) return false;
        else return true;
    } else if(p1_first > p2.first) {
        return true;
    } else if(p1_first < p2.first) {
        return false;
    } else {}
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    int len = genres.size();
    initialize(len, genres, plays);
    vector<pair<string, int>> maxTimeGenres = case1();
    int gSize = maxTimeGenres.size();
    for(int i = 0; i < gSize; ++i) {
        string str = maxTimeGenres[i].first; // 가장 많이 재생된 노래가 앞에 온다.
        // 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
        vector<pair<int, int>> v;
        for(auto iter = genresTime.lower_bound(str); iter != genresTime.upper_bound(str); ++iter) {
            // 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다.
            // 최대 2개의 곡까지 모은다.
            // 한곡만 있는 경우 한곡만 수록한다.
            v.emplace_back(make_pair(iter->second.first, iter->second.second));
        }
        
        int vSize = v.size();
        sort(v.begin(), v.end(), isFinalcmp);
        if(vSize >= 2) {
            // 장르에 2곡 이상
            answer.emplace_back(v[0].second);
            answer.emplace_back(v[1].second);
        } else {
            // 장르에 1곡만있을 때
            answer.emplace_back(v[0].second);
        }
    }
    return answer;
}