Programmers 베스트앨범 Java

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

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

노래의 장르를 나타내는 문자열 배열 genres와 노래별 재생 횟수를 나타내는 정수 배열 plays가 주어질 때, 베스트 앨범에 들어갈 노래의 고유 번호를 순서대로 return 하도록 solution 함수를 완성하세요.

제한사항

• genres[i]는 고유번호가 i인 노래의 장르입니다.
• plays[i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genresplaysreturn

["classic", "pop", "classic", "classic", "pop"]

[500, 600, 150, 800, 2500]

[4, 1, 3, 0]

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

 

---

풀이

개인적으로 많은 부분에서 배울 수 있었던 문제다. 해당 문제에서 요구하는 조건자체는 어려운 조건은 아니었지만, 해당 조건을 얼마나 효과적으로 할 수 있냐는 문제였다.

---

풀이 순서

• 조건파악
  1. 속한 노래가 많이 재생된 장르를 먼저 수록합니다.
  2. 장르 내에서 많이 재생된 노래를 먼저 수록합니다.
  3. 장르 내에서 재생횟수가 같은 노래 중에서는 고유 번호가 낮은 노래 먼저 수록합니다.
• HashMap을 이용하여 genres에 해당하는 정보와, plays에 해당하는 정보를 totalGenreMap에 저장한다.
  1. HashMap의 getOrDefault을 이용하여 plays의 값을 저장시킨다.

for (int i = 0; i < genres.length; i++) {
totalGenreMap.put(genres[i], (totalGenreMap.getOrDefault(genres[i], 0)) + plays[i]);
}

• ArrayList형태의 sortGenre를 선언하여 totalGenreMap의 key값(genre들의 String name)을 가져온다.
• 이후 Collectionsort를 이용하여 sortGenre의 내용들을 재생횟수가 큰 순서대로 정렬시켜준다.

ArrayList<String> sortGenre = new ArrayList<>(totalGenreMap.keySet());
Collections.sort(sortGenre, (o1, o2) -> totalGenreMap.get(o2).compareTo(totalGenreMap.get(o1)));

• 정렬시킨 sortGenre를 이용하여 반복을 통해 해당 genre들마다 재생횟수들을 비교한다.
  • max를 선언하여 장르 내부의 최대 재생횟수를 가져온다.
  • 여기서 index값이 장르 내부 최대 재생횟수의 앨범의 고유값으로 이용하였다.
  • 비교하는 genre에 맞추어 최대 재생횟수를 가져오고 해당 value값을 max에 index를 첫번째 album "first"에 저장한다.
  • 이후 다시 max값을 초기화 시켜주어 두번째 앨범을 첫번째 앨범의 index값을 제외하고 비교하여 가져온다.
  • genre에 해당하는 앨범이 하나일 수 있으니 max가 여전히 MIN_VALUE일 경우는 해당 genre의 앨범이 하나라 간주하고 bestAlbum에 첫번째 앨범만 넣어준다.

---

전체 소스

---

문제를 해결하며 어려웠던 점

int first = 0, second = 0;

first와 second를 초기화 시키는 부분에서 실수를 하여 꽤 긴시간을 문제를 해결하는데 오래걸렸다. sortGenre를 비교하는 for문 안에서 초기화를 시켜주는 부분을 찾고 가장 기초적이지만 초기화를 시켜주는 위치에 신경써야겠다는 생각을 했다.

 

ArrayList<String> sortGenre = new ArrayList<>(totalGenreMap.keySet());
Collections.sort(sortGenre, (o1, o2) -> totalGenreMap.get(o2).compareTo(totalGenreMap.get(o1)));

각 Genre에서 해당 재생횟수를 더하여 해당 재생횟수에 따라 정렬하는 부분에서 긴 고민시간을 가져왔다. 

이 부분에서 ArrayList의 선언과 함께 totalGenreMap.keySet()을 가져와서 비교하여 Collection.sort를 이용하여 비교하는 방법을 진행했다. 

 

초기에는 Comparable을 이용하여 별도의 class를 선언하여 이용하고자 했지만 단순 정렬에 있어서 Collection.sort를 사용하는 방식도 효과적으로 코드를 줄일 수 있는 방법으로 알게되어 문제에 적용하였다. 

 

다른 사람의 코드를 보며 해당 소스에서도 참고할 부분이 많았다.