티스토리 뷰
이문제는 해시와 정렬을 이용해 풀 수 있는 문제였다. 깔끔하게 풀고 싶었으나 답이 나오게 문제를 풀기만 한 것 같다...ㅎ
문제풀이
-장르별로 어떤 노래가 있는지 구분하기 위해 Map을 이용해 저장해준다.
-각 장르 안에서 노래들은 재생 횟수가 높은 순, 같은 재생 횟수일 경우 고유번호(인덱스가 사용됨)가 낮은 순으로 저장할 수 있도록 PriorityQueue를 사용하고 정렬 기준을 정해주기 위해 compareTo함수를 구현해 준다.
-장르별 재생 횟수를 구해서 가장 높은 재생 횟수를 기록하는 장르가 먼저 앨범에 수록될 수 있도록 장르(key), 장르별 재생 횟수(value)로 저장한 후 정렬해 준다.
-**여기서 내가 헷갈렸던 부분은 각 장르별 2개 노래를 뽑는데, 장르별 재생 횟수를 구할 때는 2개가 아닌 장르에 해당하는 전체 노래의 재생 횟수를 더해야 한다는 부분!
-그 후에 재생 횟수로 정렬한 맵에서 해당 장르의 노래를 2개씩 뽑아와 정답 배열에 순서대로 저장한다.
-**여기서도 고려해야 될 부분! 해당 장르의 노래가 2개가 아니고 1개일 수 있다. 이 부분을 고려하여 처리해줘야 한다.
import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.TreeMap;
public class Solution {
public static void main(String[] args) {
String[] genres= {"classic", "pop", "classic", "classic", "pop","zazz","zazz"};
int[] plays = {500, 600, 150, 800, 2500,4000,100};
int ansSize=0;
HashMap<String,PriorityQueue<Song>> map = new HashMap<>();
//장르,장르에 해당하는 노래로 map에 저장
for(int i=0;i<plays.length;i++) {
PriorityQueue<Song> list;
if(map.containsKey(genres[i])) {
list = map.get(genres[i]);
if(map.get(genres[i]).size()==1) ansSize++;
}else {
list = new PriorityQueue<>();
ansSize++;
}
list.add(new Song(i,plays[i]));
map.put(genres[i], list);
}
int[] answer = new int[ansSize];
//장르별 총 재생횟수를 세어 장르와 함께 저장하고 내림차순 될 수 있도록 정렬구현
Comparator<Integer> comparator = (o1, o2)->o2.compareTo(o1);
Map<Integer, String> sortingMap = new TreeMap<>(comparator);
for(String key : map.keySet()) {
int sum = 0;
int size = map.get(key).size();
PriorityQueue<Song> val = new PriorityQueue<Song>();
for(int i=0;i<size;i++) {
Song song = map.get(key).poll();
sum += song.play;
val.add(song);
}
map.put(key, val);
sortingMap.put(sum, key);
}
//위에서 재생횟수로 정렬된 key값인 장르를 꺼내어
//처음에 정보가 저장된 map에서 노래를 뽑아 answer배열에 저장한다
int index=0;
for(Integer i : sortingMap.keySet()) {
String key = sortingMap.get(i);
if(map.get(key).size()==1) {
answer[index++] = map.get(key).poll().no;
}else {
answer[index++] = map.get(key).poll().no;
answer[index++] = map.get(key).poll().no;
}
}
for(int i : answer) {
System.out.println(i);
}
}
}
class Song implements Comparable<Song>{
int no;
int play;
Song(int no, int play){
this.no = no;
this.play = play;
}
public int compareTo(Song s) {
if(this.play > s.play) {
return -1; // 내림차순
}
else if(this.play== s.play) {
if(this.no < s.no) {
return -1;
}
}
return 1;
}
}
'CS공부 > 알고리즘&문제풀이' 카테고리의 다른 글
[백준 15683]감시/삼성 sw역량 테스트 기출(java) (0) | 2020.08.12 |
---|---|
[프로그래머스]DP:정수 삼각형(java) (0) | 2020.08.06 |
[프로그래머스]해시:위장(java) (2) | 2020.07.29 |
[프로그래머스]DP:N으로 표현(java) (0) | 2020.07.26 |
[백준 17837]새로운 게임2/삼성 sw역량 테스트 기출(java) (0) | 2020.07.24 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Stomp
- 삼성 sw역량테스트
- 코딩테스트
- 완전탐색
- git
- MST
- 운영체제
- Spring
- SWEA
- 삼성 sw역량 테스트
- Baekjoon
- dfs
- java
- 프로그래머스
- Oracle
- 최소 스패닝 트리
- JavaScript
- 분리 집합
- DP
- BFS
- sockjs
- websocket
- 자바
- Heap
- OS
- 백준
- programers
- 채팅
- 정렬
- 알고리즘
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
글 보관함