[프로그래머스] 베스트 앨범

AngJ·어제

구현 정렬 코딩테스트 프로그래머스 해시

코딩테스트

목록 보기

14/15

문제

Programmers_베스트앨범

요약

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

정렬 우선순위 1 : 가장 많이 재생된 장르순
정렬 우선순위 2 : 장르 내에서 가장 많이 재생된 노래순
정렬 우선순위 3 : 고유 번호가 낮은 노래순

접근

문제를 처음 보자마자 노래를 지칭하는 객체를 하나 만들고, 그 객체에 대해서 언급된 우선순위에 맞게 정렬하면 해결될 것이라는 생각을 했다.
여기서 가장 중요하게 느껴졌던 점은 노래 객체를 저장할 자료구조를 선정하는 것이었다.
그리고, 우선순위 정렬을 하는 방법을 알고 있느냐, 익숙하게 다룰 수 있느냐 또한 중요한 것으로 보였다.

장르별 노래 플레이 횟수가 저장되도록하기 위해 key를 genre, value를 play로 하는 Map을 사용했고, 이를 활용해 먼저 정렬되어야 하는 기준을 잡았다.
그리고 Music 배열을 map.size()만큼 만들어서 그 배열을 Comparator의 compare 함수를 오버라이드해서 쓰면 해결될 것이라 생각하고 접근했다.

알고리즘

genre, play, 고유 번호를 저장하는 Music 클래스를 만든다.
for문으로 돌면서 Music 객체를 만들고, 이 객체의 genre와 play 값을 활용해 Map에 값을 누적시킴과 동시에 Music 배열에 그 객체를 집어 넣는다.
Array.sort()를 하면서, Comparator 인터페이스를 활용해 문제의 기준에 맞게 정렬되도록 만든다. (이때, map을 함께 활용해 우선순위를 정렬하는 것이 핵심!)
정렬된 Music 배열을 순회하면서 장르별 정렬 기준에 맞게 상위 2개 이하씩 뽑히도록 돈다.
최종적으로 result 배열을 출력한다.

제출 코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        // 총 음악 개수
        int len = genres.length;
        Music[] musics = new Music[len];
        // 장르별 노래 개수 저장
        Set<String> set = new HashSet<>();
        Map<String, Integer> map = new HashMap<>();
        
        // 장르 종류 저장
        for (int i = 0; i < len; i++) {
            set.add(genres[i]);
        }
        // 장르 개수 저장
        for (String genre : set) {
            map.put(genre, 0);
        }
        
        for (int i = 0; i < len; i++) {
            String genre = genres[i]; // 현재 인덱스의 장르
            musics[i] = new Music(genre, plays[i], i);
            map.put(genre, map.get(genre)+plays[i]);
            // map.put(genre, map.getOrDefault(genre, 0)+plays[i]); // Set을 쓰지 않고 해결 가능
        }
        
        // 3가지 정렬 기준에 맞춰서 정렬 (Comparable)
        Arrays.sort(musics, new Comparator<Music>() {
            @Override
            public int compare(Music a, Music b) {
                if (a.genre.equals(b.genre)) {
                    if (a.play == b.play) {
                        return a.idx - b.idx;
                    }
                    return b.play - a.play;
                }
                return map.get(b.genre).compareTo(map.get(a.genre));
            }
        });
        
        List<Integer> answer = new ArrayList<>();
        
        String genre = "";
        // 정렬된 배열을 끝까지 돔
        for (int i = 0, cnt = 0; i < musics.length; i++) {
            // 이전 곡과 같은 장르인 경우
            if (genre.equals(musics[i].genre)) {
                // 이미 2곡을 선택했다면 다음으로 이동
                if (cnt == 2) {
                    continue;
                }
                // 2곡 선택되지 않았다면 해당 앨범의 인덱스 추가
                else {
                    cnt++;
                    answer.add(musics[i].idx);
                }
            }
            // 새로운 장르인 경우
            else {
                cnt = 1;
                genre = musics[i].genre;
                answer.add(musics[i].idx);
            }
        }
        
        int[] arr = new int[answer.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = answer.get(i);
        }
        return arr;
    }
    public static class Music {
        String genre;
        int play;
        int idx;

        public Music(String genre, int play, int idx) {
            this.genre = genre;
            this.play = play;
            this.idx = idx;
        }
    }
}

// 알고리즘 
// 자료구조 : Class와 Array 사용하면 풀릴 것 같다.
// 조건 
// Class를 먼저 정렬한다. 그 후 노래별 재생횟수로 정렬한다.

어려웠던 점

Comparator 인터페이스를 활용해 다중 정렬을 사용하는게 처음이라 문법이 조금 어색하고 어려웠다. 특히 map을 활용해 정렬을 한다는 걸 스스로 알아내기까지 시행착오가 많았다.

상위 2개를 뽑고 나머지는 뽑지 않아야하는 걸 구현하는데 생각보다 애를 먹었다.
cnt를 올리다가 2가 되고, 장르가 같다면 continue 치면 되는건데, 어렵게 index 를 점프 시키려고 하다가 코드가 좀 꼬인 부분이 있었다. 시간을 줄이려고 한거지만, 실제 시험에서는 이 생각보단 가장 컴팩트하게 해결할 수 있는 방법으로 접근한 뒤 시간 초과가 발생하면 이 방식으로 접근해보자!