프로그래머스 문제풀이, 베스트앨범
07 Jun 2019 | HashMap java Programmers프로그래머스 문제풀이 - 베스트 앨범
문제 설명
문제설명 바로가기
- 제한조건
- genres[i]는 고유번호가 i인 노래의 장르입니다.
- plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
- genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
- 장르 종류는 100개 미만입니다.
- 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
- 모든 장르는 재생된 횟수가 다릅니다.
- 어렵게 풀었다, 정렬을 많이 써서 풀었는데 다른 방법이 생각이 나지 않아서 4시간 정도 고민한거 같다
- 경우의수가 크지않아서 거이 대부분의 조건을 구현하고, 정렬했다.
- compareTo를 많이 활용했다, 이미 체크한 배열은 boolean으로 다시 체크하지않게 처리했는데 어째 뺀게 시간이 더 빠르다
import java.util.*;
class Solution {
public int[] solution(String[] genres, int[] plays){
int[] answer = {};
List<Integer> list = new ArrayList<>();
boolean[] check = new boolean[10000];
HashMap<String,Integer> map = new HashMap<>();
PriorityQueue<Pair> priorityQueue = new PriorityQueue<>();
// 제한이 100개..
// 가장 많이 속한 장르를 구하자!!
for(int i=0; i<genres.length; i++){
if(map.containsKey(genres[i])) {
map.put(genres[i], map.get(genres[i])+plays[i]);
} else {
map.put(genres[i],plays[i]);
}
}
// classic = 3
// pop = 2
// map을 정렬해보자..
List<String> keyList = new ArrayList<>(map.keySet());
Collections.sort(keyList, new Comparator<String>(){
@Override
public int compare(String o1, String o2){
return map.get(o2).compareTo(map.get(o1));
}
});
for(String key : keyList){
for(int i=0; i<genres.length; i++){
if(genres[i].contains(key) && !check[i]){
check[i] = true;
priorityQueue.offer(new Pair(i,plays[i]));
}
if(i == genres.length - 1){
for(int k=0; k<2; k++){
if(priorityQueue.isEmpty()){
break;
}
list.add(priorityQueue.poll().location);
}
priorityQueue.clear();
}
}
}
return list.stream().mapToInt(Integer::intValue).toArray();
}
public class Pair implements Comparable<Pair>{
private int location;
private int plays;
public Pair(int location, int plays){
this.location = location;
this.plays = plays;
}
@Override
public int compareTo(Pair pair){
if(this.plays > pair.plays){
return -1;
} else if(this.plays < pair.plays){
return 1;
} else {
return 0;
}
}
}
}
Comments