99클럽 코테 스터디 5일차 TIL + Java Algorithm

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

문제 & 키워드

• 프로그래머스 - 베스트 앨범 (문제 링크)
• 정렬
• 스트림

문제 설명

여러 장르의 노래들이 있습니다. 각 노래는 고유한 번호로 구분됩니다. 노래를 수록하는 기준은 다음과 같습니다.

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

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

제한사항

• genres 배열의 길이는 1 이상 10,000 이하입니다.
• genres[i]는 고유번호 i의 노래의 장르입니다.
• plays 배열의 길이는 genres 배열의 길이와 같으며, 0 이상 10,000 이하의 정수를 갖습니다.
• 장르에 속한 노래가 하나라면, 그 노래만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genres plays return

["classic", "pop", "classic", "classic", "pop"]	[500, 600, 150, 800, 2500]	[4, 1, 3, 0]
["classic", "pop", "classic", "classic", "pop", "jazz"]	[500, 600, 150, 800, 2500, 1000]	[4, 1, 5, 3, 0]

입출력 예 설명

1. classic 장르는 1,450회 재생되었고, pop 장르는 3,100회 재생되었습니다. 따라서 pop 장르가 먼저 수록됩니다.
2. pop 장르에서는 "pop" 노래가 2,500회 재생되어 가장 많이 재생되었고, 그 다음으로 "pop" 노래가 600회 재생되었습니다.
3. classic 장르에서는 "classic" 노래가 800회 재생되어 가장 많이 재생되었고, 그 다음으로 "classic" 노래가 500회 재생되었습니다.
4. 따라서 결과는 [4, 1, 3, 0]입니다.

문제 풀이

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        List<Album> albumList = new ArrayList<>();

        for (int i = 0; i < genres.length; i++) {
            String genre = genres[i];
            int play = plays[i];
            albumList.add(new Album(i, genre, play));
        }

        Map<String, Integer> albumMap = albumList.stream()
                .collect(
                        Collectors.groupingBy(
                                Album::getGenres,
                                Collectors.summingInt(Album::getPlays)
                        ));

        List<Map.Entry<String, Integer>> sortedGenres = albumMap.entrySet().stream()
                .sorted((o1, o2) -> o2.getValue() - o1.getValue())
                .collect(Collectors.toList());

        List<Integer> result = new ArrayList<>();

        for (Map.Entry<String, Integer> entry : sortedGenres) {
            List<Album> sortedAlbums = albumList.stream()
                    .filter(album -> album.getGenres().equals(entry.getKey()))
                    .sorted((o1, o2) -> {
                        if (o2.getPlays() == o1.getPlays()) {
                            return o1.getAlbumId() - o2.getAlbumId();
                        }
                        return o2.getPlays() - o1.getPlays();
                    })
                    .collect(Collectors.toList());

            Iterator<Album> iterator = sortedAlbums.iterator();
            int count = 0;
            while (iterator.hasNext() && count < 2) {
                result.add(iterator.next().getAlbumId());
                count++;
            }
        }

        return result.stream().mapToInt(i -> i).toArray();
    }

    class Album {
        private final int albumId;
        private final String genres;
        private final int plays;

        public Album(int albumId, String genres, int plays) {
            this.albumId = albumId;
            this.genres = genres;
            this.plays = plays;
        }

        public int getAlbumId() {
            return albumId;
        }

        public String getGenres() {
            return genres;
        }

        public int getPlays() {
            return plays;
        }
    }
}

풀이 설명

1. 노래 정보 저장
   • Album 클래스는 노래의 고유번호, 장르, 재생 횟수를 저장합니다.
   • 주어진 genres 배열과 plays 배열을 순회하며 Album 객체를 생성하고 albumList에 저장합니다.
2. 장르별 재생 횟수 합산
   • 스트림을 이용해 장르별 재생 횟수 합계를 계산하고 이를 albumMap에 저장합니다.
   • Collectors.groupingBy와 Collectors.summingInt를 이용하여 장르별 재생 횟수를 합산합니다.
3. 장르별 노래 정렬
   • albumMap의 엔트리를 재생 횟수 합계에 따라 내림차순으로 정렬합니다.
   • 각 장르별로 노래를 필터링하고, 재생 횟수 내림차순, 재생 횟수가 같으면 고유번호 오름차순으로 정렬합니다.
4. 베스트 앨범 구성
   • 정렬된 장르 순서대로 최대 2개의 노래를 선택하여 결과 리스트에 추가합니다.
   • 최종적으로 결과 리스트를 배열로 변환하여 반환합니다.

---

마무리하며

• 이번 문제를 통해 자바의 스트림과 컬렉션을 활용한 데이터 처리 방법을 연습할 수 있었습니다.
• 장르별로 데이터를 그룹화하고 정렬하는 과정에서 스트림의 강력한 기능을 활용했습니다.
• 코드의 가독성과 성능을 고려하여 효율적으로 문제를 해결하는 방법을 고민해볼 수 있었습니다.