[프로그래머스] 베스트앨범

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

풀이

상당히 구현하기 까다로운 문제이다. Map을 사용해 장르 별 재생 횟수를 체크하고, 또 하나의 Map을 통해서 동일 장르의 음악 재생 횟수를 저장한 뒤, 별도의 정렬함수의 구현을 통해 해결했다.

코드

C++

#include <string>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

struct Song {
    string genre;
    int count;
};

bool cmp(Song& a, Song& b) {
    return a.count > b.count;
}

bool cmp2(pair<int, int>& a, pair<int, int>& b) {
    if (a.first > b.first) return true;
    else if (a.first == b.first && a.second < b.second) return true;
    return false;
}

vector<int> solution(vector<string> genres, vector<int> plays) {
    vector<int> answer;
    map<string, int> genre;
    map<string, vector<pair<int, int>>> song;
    for (int i = 0; i < genres.size(); i++) {
        genre[genres[i]] += plays[i];
        song[genres[i]].push_back({ plays[i], i });
    }
    vector<Song> arr;
    for (auto it : genre) arr.push_back({ it.first, it.second });
    sort(arr.begin(), arr.end(), cmp);
    for (int i = 0; i < arr.size(); i++) {
        string g = arr[i].genre;
        sort(song[g].begin(), song[g].end(), cmp2);
        if (song[g].size() < 2) {
            answer.push_back(song[g][0].second);
            continue;
        }
        for(int j=0; j<2; j++) answer.push_back(song[g][j].second);
    }
    return answer;
}

Java

import java.util.*;

class Pair {
    int first, second;

    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }
}

class Song {
    String genre;
    int count;

    public Song(String genre, int count) {
        this.genre = genre;
        this.count = count;
    }
}

class Solution {
    Comparator<Pair> comp = (o1, o2) -> {
        if (o1.first > o2.first) return -1;
        else if (o1.first == o2.first && o1.second < o2.second) return -1;
        return 1;
    };

    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, Integer> genre = new HashMap<>();
        HashMap<String, ArrayList<Pair>> song = new HashMap<>();
        for (int i = 0; i < genres.length; i++) {
            genre.put(genres[i], genre.getOrDefault(genres[i], 0) + plays[i]);
            if (!song.containsKey(genres[i])) song.put(genres[i], new ArrayList<>());
            song.get(genres[i]).add(new Pair(plays[i], i));
        }
        ArrayList<Song> arr = new ArrayList<>();
        for (String it : genre.keySet()) arr.add(new Song(it, genre.get(it)));
        arr.sort((o1, o2) -> {
            if (o1.count > o2.count) return -1;
            return 1;
        });

        ArrayList<Integer> tmp = new ArrayList<>();
        for (Song s : arr) {
            String g = s.genre;
            song.get(g).sort(comp);
            if (song.get(g).size() < 2) {
                tmp.add(song.get(g).get(0).second);
                continue;
            }
            for (int i = 0; i < 2; i++)
                tmp.add(song.get(g).get(i).second);
        }
        int[] answer = new int[tmp.size()];
        for (int i = 0; i < tmp.size(); i++) answer[i] = tmp.get(i);
        return answer;
    }
}