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

※ 해당 문제의 링크는 여기입니다. ※

 

다른 분들이 푸신 방법도 보았으나

내부 클래스 만드셔서 하시는 경우가 대부분이었으나

저는 HashMap 3개를 만들어 해결하였습니다.

 

3가지 조건을 충족하기 위해 HashMap을 만들었습니다.

각각의 HashMap은

장르, 재생 횟수 / 장르, 총 재생 횟수 / 고유 번호, 재생 횟수 로 하였습니다.

HashMap<String, ArrayList<Integer>> songs = new HashMap<>();        // 장르, 횟수
HashMap<String, Integer> heardTimes = new HashMap<>();              // 장르, 총 횟수
HashMap<Integer, Integer> unique = new HashMap<>();                 // 고유 번호, 횟수

장르를 키로 몇 번 재생한 횟수를 저장을 for문을 사용하여 저장하였습니다.

for (int i = 0; i < genres.length; i++) {
    // 장르를 키로 몇 번 들었는 지 넣기
    if (songs.containsKey(genres[i])) {
        songs.get(genres[i]).add(plays[i]);
    }
    else {
        songs.put(genres[i], new ArrayList<>());
        songs.get(genres[i]).add(plays[i]);
    }
    heardTimes.put(genres[i], heardTimes.getOrDefault(genres[i], 0) + plays[i]);
    unique.put(i, plays[i]);
}

 

그런 후, 임시 List를 만들어 정렬을 하여 첫 번째 조건인

속한 노래가 많이 재생된 장르를 먼저 수록합니다.

를 해결합니다.

ArrayList<Integer> answer = new ArrayList<>();
List<String> genreList = new ArrayList<>(heardTimes.keySet());

genreList.sort((o1, o2) -> (heardTimes.get(o2).compareTo(heardTimes.get(o1)))); // 내림차순으로 정렬

그 이후

2번째, 3번째 조건을 해결하도록 합니다.

for (String key : genreList) {

    if (songs.get(key).size() == 1) {
        for (int i : unique.keySet()) {
            if (answer.contains(i)) {
                continue;
            }

            if (Objects.equals(songs.get(key).get(0), unique.get(i))) {
                answer.add(i);
                break;
            }
        }
    }
    else {
        // 횟수가 많으면 선택됨
        // 해당 key 로 arrayList 정렬 (내림차순)
        songs.get(key).sort(Comparator.reverseOrder());
        for (int j = 0; j < 2; j++) {
            for (int i : unique.keySet()) {
                if (answer.contains(i)) {
                    continue;
                }

                if (Objects.equals(songs.get(key).get(j), unique.get(i))) {
                    answer.add(i);
                    break;
                }
            }
        }
    }
}

if (song.get(key). size() == 1) 조건을 따로 건 이유는원소가 하나뿐인데, 내림차순을 하는 것은 시간 낭비라고 생각하였기 때문입니다.

 

그리고 unique의 key들은 맨 처음 for문에서 순차적으로 저장을 시켰으므로

3번 역시 해결하였습니다.

 

그리고 answer.contains(i)를 추가한 이유는 중복이 될 수도 있기 때문입니다.

int[] result = new int[answer.size()];
for(int i = 0; i < answer.size(); i++) {
    result[i] = answer.get(i);
}
System.out.println(Arrays.toString(result));
return result;

최종적으로 배열에 값을 넣고 반환해주면 끝납니다.

 

전체 소스코드

import java.util.*;

class Solution {
    public int[] solution(String[] genres, int[] plays) {
        HashMap<String, ArrayList<Integer>> songs = new HashMap<>();        // 장르, 횟수
        HashMap<String, Integer> heardTimes = new HashMap<>();              // 장르, 총 횟수
        HashMap<Integer, Integer> unique = new HashMap<>();                 // 고유 번호, 횟수
        for (int i = 0; i < genres.length; i++) {
            // 장르를 키로 몇 번 들었는 지 넣기
            if (songs.containsKey(genres[i])) {
                songs.get(genres[i]).add(plays[i]);
            }
            else {
                songs.put(genres[i], new ArrayList<>());
                songs.get(genres[i]).add(plays[i]);
            }
            heardTimes.put(genres[i], heardTimes.getOrDefault(genres[i], 0) + plays[i]);
            unique.put(i, plays[i]);
        }

        ArrayList<Integer> answer = new ArrayList<>();
        List<String> genreList = new ArrayList<>(heardTimes.keySet());

        genreList.sort((o1, o2) -> (heardTimes.get(o2).compareTo(heardTimes.get(o1)))); // 내림차순으로 정렬
        for (String key : genreList) {

            if (songs.get(key).size() == 1) {
                for (int i : unique.keySet()) {
                    if (answer.contains(i)) {
                        continue;
                    }

                    if (Objects.equals(songs.get(key).get(0), unique.get(i))) {
                        answer.add(i);
                        break;
                    }
                }
            }
            else {
                // 횟수가 많으면 선택됨
                // 해당 key 로 arrayList 정렬 (내림차순)
                songs.get(key).sort(Comparator.reverseOrder());
                for (int j = 0; j < 2; j++) {
                    for (int i : unique.keySet()) {
                        if (answer.contains(i)) {
                            continue;
                        }

                        if (Objects.equals(songs.get(key).get(j), unique.get(i))) {
                            answer.add(i);
                            break;
                        }
                    }
                }
            }
        }

        int[] result = new int[answer.size()];
        for(int i = 0; i < answer.size(); i++) {
            result[i] = answer.get(i);
        }
        System.out.println(Arrays.toString(result));
        return result;
    }
}

Objects.equals를 사용을 한 이유는 == 기호를 사용할 경우,

주소 값으로 비교하기 때문에 equals를 사용하여 비교하여야 합니다.

String을 비교할 때 equals를 사용하는 이유와 동일합니다.

추가로...

테스트 케이스가 하나뿐이기에개인적으로 해결하는 데에 있어 약간 난관이 있었습니다.

 

그래서 이 글을 읽으시는 분들에게 조금이나마 도움을 드리고자테스트 케이스 3가지 정도 작성하고자 합니다.

 

genres, plays, output 순서입니다.

["classic", "pop", "classic", "classic", "pop", "rap"], [500, 600, 150, 800, 2500, 200], [4, 1, 3, 0, 5]
["classic", "pop", "rap", "classic", "classic"], [100, 300, 200, 150, 100], [3, 0, 1, 2]
["classic", "pop", "rap", "classic", "classic", "pop"], [100, 200, 300, 100, 100, 200], [1, 5, 2, 0, 3]

 

이상입니다.