프로그래머스_베스트앨범(C++, JAVA)

 

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

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

[문제 풀이]

map을 이용하여 문제를 풀었습니다.

이 문제는 아래의 조건을 만족하는 값을 찾는 것입니다.

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

주의할 점은 같은 장르 안에서는 최대 2개까지만 선택할 수 있다는 것입니다. 예를 들어 classic 장르가 [500, 150, 800]과 같이 세 번 재생되었으면 [800, 500] 두 개만 수록할 수 있다는 것입니다.

 

로직을 설명해 드리겠습니다.

1. 재생된 장르의 총횟수를 genres_total 맵에 저장합니다.
2. genres_total 맵의 값들을 copy_total에 저장하여 정렬합니다.
3. 재생된 목록들이 재생된 횟수와 인덱스 번호와 재생된 횟수를 v 벡터에 저장한 후 정렬합니다.
4. 장르의 크기(copy_total.size())를 순회하며 v의 장르 이름이 copy_total 이름과 같다면 두 개까지 answer에 저장해줍니다.

[C++]

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

using namespace std;

bool comparePair(pair<string, int> a, pair<string, int> b){
    return a.second > b.second;
}

bool compare(tuple<string, int, int> a, tuple<string, int, int> b){
    return get<1>(a) > get<1>(b);
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> genres_total;
    vector<pair<string, int>> copy_total;
    vector<tuple<string, int, int>> v;
    
    for(int i = 0; i < genres.size(); i++)
        genres_total[genres[i]] += plays[i];
    
    for(auto iter = genres_total.begin(); iter != genres_total.end(); iter++)
        copy_total.push_back(make_pair(iter->first, iter->second));
    
    for(int i = 0; i < genres.size(); i++){
        v.push_back(make_tuple(genres[i], plays[i], i));
    }
    
    sort(copy_total.begin(), copy_total.end(), comparePair);
    sort(v.begin(), v.end(), compare);
    
   for(int i = 0; i < copy_total.size(); i++){
       int num = 0;
       for(int j = 0; j < v.size(); j++){
           if(get<0>(v[j]) == copy_total[i].first){
               answer.push_back(get<2>(v[j]));
               num++;
           }
           if(num == 2)
               break;
           
       }
   }
    
    return answer;
}

 

[JAVA]

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

class Solution{
	
	class Music{
		String genre;
		int playNum;
		int idx;
		
		Music(String genre, int playNum, int idx){
			this.genre = genre;
			this.playNum = playNum;
			this.idx = idx;
		}
		
		Integer getPlayNum() {
			return playNum;
		}
	}
	
    public int[] solution(String[] genres, int[] plays) {
        int[] answer = {};
        
        Map<String, Integer> totalMap = new HashMap<>();
        ArrayList<Music> musicList = new ArrayList<>();
        
        for(int i = 0; i < genres.length; i++) {
        	totalMap.put(genres[i], totalMap.getOrDefault(genres[i], 0) + plays[i]);
        	musicList.add(new Music(genres[i], plays[i], i));
        	
        }
        
        List<Entry<String, Integer>> totalList = new ArrayList<Entry<String, Integer>>(totalMap.entrySet());
        
        Collections.sort(totalList, new Comparator<Entry<String, Integer>>(){
        		public int compare(Entry<String, Integer> obj1, Entry<String, Integer> obj2) {
        			return obj2.getValue().compareTo(obj1.getValue());
        		}
        	}
        );
        
        Collections.sort(musicList, new Comparator<Music>(){
        	public int compare(Music obj1, Music obj2) {
        		return obj2.getPlayNum().compareTo(obj1.getPlayNum());
        	}
        });
        
        List<Integer> answerList = new ArrayList<>(); 
        
        for(int i = 0; i < totalList.size(); i++) {
        	int num = 0;
        	for(int j = 0; j < musicList.size(); j++) {
        		if(totalList.get(i).getKey().equals(musicList.get(j).genre)) {
        			answerList.add(musicList.get(j).idx);
        			num++;
        		}
        		if(num == 2)
        			break;
        	}
        }
        
        answer =  answerList.stream().mapToInt(Integer::intValue).toArray();
        
        return answer;
    }
}