프로그래머스 - 베스트앨범

프로그래머스 - 베스트앨범

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

객체에 comparable<>를 implements 하여 정렬을 할 수 있다.

해당 문제를 comparable<>을 사용하여 풀어보았다.

먼저 필요한 자료구조를 생각해보면

1. 곡의 고유번호와 플레이 횟수를 담고 있는 객체

2. 장르별로 재생횟수를 합하여 어떤 장르를 많이 듣는지를 확인하기 위한 map.

3. 장르와 장르별 곡 객체의 리스트들을 갖고 있는 map.

이 필요하다.

노래 객체를 다음과 같이 만들었다.

class Song implements Comparable{ int id; int play; Song(int id, int play){ this.id = id; this.play = play; } @Override public int compareTo(Song o){ if(o.play == this.play) return this.id - o.id; else return o.play - this.play; } }

※ 객체에 comparable<> interface를 이용함으로써 compareTo 메서드를 override하여 원하는 순서로 정렬을 할 수 있다.

정렬 규칙은 this객체와 파라미터로 전달받은 객체를 비교하여 정해진다.

return 값이 양수일 경우 두 객체의 위치가 바뀌게 되는데 이를 이용하여 내림차순인지 오름차순인지 정할 수 있다.

따라서 o.play - this.play를 리턴 하게되면 뒤의 객체(파라미터로 전달받은 객체) 가 더 클 때에는 자리가 바뀌고 , o.play가 작을 경우에는 음수이므로 자리를 바꾸지 않기 때문에 내림차순이 된다. 반대로 this.play - o.play 를 리턴하게 되면 앞 객체가 클 경우 자리가 바뀌므로 오름차순이 된다.

해당 문제에서 play횟수가 같을 경우 낮은 고유번호 순으로 받는다고 하였기 때문에 재생횟수가 같을 경우 고유번호를 비교하는 구문을 추가하였다.

sort는 다음과 같이 적용 할 수 있다.

Collections.sort(list);

문제는 다음과 같이 해결하였다.

처음 genres 배열과 plays 배열을 함께 돌면서 map과 재생횟수 합을 구한다.

재생횟 수 합이 가장 큰 순서로 map을 정렬한다.

가장 재생횟수가 많은 장르 부터, 그 장르의 노래들을 내림차순으로 정렬하고 가장 재생횟수가 많은 노래를 2개씩 순서대로 리스트에 넣는다.

public int[] solution(String[] genres, int[] plays) { int[] answer = {}; HashMap> map = new HashMap<>(); HashMap totalPlay = new HashMap<>(); ArrayList res = new ArrayList<>(); for(int i = 0 ;i < genres.length; i++){ if(map.containsKey(genres[i])){ map.get(genres[i]).add(new Song(i, plays[i])); totalPlay.put(genres[i], totalPlay.get(genres[i]) + plays[i]); } else { List list = new ArrayList<>(); list.add(new Song(i, plays[i])); map.put(genres[i], list); totalPlay.put(genres[i], plays[i]); } } List> entityList = new ArrayList<>(totalPlay.entrySet()); entityList.sort((o1, o2) -> totalPlay.get(o2.getKey()) - totalPlay.get(o1.getKey())); for(int i = 0 ;i < entityList.size(); i++){ List temp = map.get(entityList.get(i).getKey()); Collections.sort(temp); for(int j = 0 ;j < temp.size(); j++){ res.add(temp.get(j).id); if(j == 1){ break; } } } answer = new int[res.size()]; for(int i = 0 ;i < res.size(); i++){ answer[i] = res.get(i); } return answer; }

여기서 사용한 것이 Map을 value값이 따라 정렬하는 것을 사용하였다.

Map을 key 값으로 정렬하기 위해서는 TreeMap을 사용하는 방법이 있고, comparator를 이용하여 정렬을 할 수 있다. value 값으로 정렬하려면 동일하게 comparator를 사용하여 정렬할 수 있다.

import java.util.*; class Main{ public static void main(String[] args) { HashMap map = new HashMap<>(); map.put("orange", 3); map.put("banana", 2); map.put("apple",5); map.put("melon",4); map.put("grape", 1); //정렬 List> entryList = new ArrayList<>(map.entrySet()); Collections.sort(entryList, new Comparator>(){ public int compare(Map.Entry o1, Map.Entry o2){ return o1.getKey().compareTo(o2.getKey()); } }); //출력 for (Map.Entry entry : entryList) { System.out.println(entry.getKey() + " : " + entry.getValue()); } } }

위 방법은 comparator를 사용하여 key값에 따라 정렬한 것이다. value값으로 정렬하려면 getKey를 getValue로 바꾸면 된다.

import java.util.*; class Main{ public static void main(String[] args) { HashMap map = new HashMap<>(); map.put("orange", 3); map.put("grape", 1); map.put("apple",5); map.put("banana", 2); map.put("melon",4); List> entryList = new ArrayList<>(map.entrySet()); entryList.sort((o1,o2)-> o1.getKey().compareTo(o2.getKey())); for (Map.Entry entry : entryList) { System.out.println(entry.getKey() + " : " + entry.getValue()); } } }

이처럼 람다식으로 변형하여 사용할 수 있다.

이번 문제는 해쉬를 사용하고 해쉬를 정렬하여 푸는 문제였다.

from http://woodimora.tistory.com/2 by ccl(A) rewrite - 2021-09-10 19:01:47