프로그래머스[Java] - 베스트앨범(해시)

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

코딩테스트 연습 - 베스트앨범

 

 

틀린 코드

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public static int[] solution(String[] genres, int[] plays) {
        List<Integer> list = new ArrayList<>();
        int length = genres.length;
        Map<String, Integer> map = getSumOfGenres(genres, plays);
        Album[] albums = getAlbums(genres, plays, map);

        // 1) 재생 노래 횟수가 같을경우 => 고유 번호가 낮은 순으로 오름차순
        // 2) 재생된 장르 수가 같을경우 => 재생 노래 횟수 순 내림차순
        // * 재생된 장르 수 -> 장르 내에서 재생된 노래 횟수 -> 노래 별 고유 번호(index) 순
        Arrays.sort(albums, (i1, i2) -> {
            if (i2.sum == i1.sum) {
                if (i2.plays == i1.plays) {
                    return Integer.compare(i1.index, i2.index);
                }
                return Integer.compare(i2.plays, i1.plays);
            }
            return Integer.compare(i2.sum, i1.sum);
        });

        int count = 1;
        list.add(albums[0].index);
        
        // 잘못된 로직 !!
        for (int i = 1; i < length; i++) {
            if (count == 2) {
                if (albums[i].genres.equals(albums[i - 1].genres)) continue;
                else count = 0;
            }

            list.add(albums[i].index);
            count ++;
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    private static Album[] getAlbums(String[] genres, int[] plays, Map<String, Integer> map) {
        Album[] albums = new Album[genres.length];

        for (int i = 0; i < genres.length; i++) {
            Album album = new Album(genres[i], plays[i], map.get(genres[i]), i);
            albums[i] = album;
        }
        return albums;
    }

    private static Map<String, Integer> getSumOfGenres(String[] genres, int[] plays) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < genres.length; i++) {
            map.put(genres[i], map.getOrDefault(genres[i], 0) + plays[i]);
        }
        return map;
    }

    static class Album {
        String genres;
        int plays;
        int sum;
        int index;

        private Album() {
        }

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

        @Override
        public String toString() {
            return "Album{" +
                    "genres='" + genres + '\'' +
                    ", plays=" + plays +
                    ", sum=" + sum +
                    ", index=" + index +
                    '}';
        }
    }
}

 

위 코드는  테스트케이스 9번만 실패하는데, 정확한 반례를 찾지 못했지만 다음과 같은 테스트케이스에서 문제가 있을 것 같습니다.

genre = 'a', 'b', 'c', 'd', 'e'

 

즉, 장르는 모두 다르지만 위 로직에서는 count == 2 일때만 if문을 탄 뒤 이전에 출시한 장르와 현재 출시한 장르를 비교하기 때문에

이러한 부분에서 실패하는 케이스가 존재할거라고 생각을 했습니다!

 

 

 

정답 코드

package kit.hash;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

// TODO:
public class 베스트앨범 {
    public static int[] solution(String[] genres, int[] plays) {
        List<Integer> list = new ArrayList<>();
        int length = genres.length;
        Map<String, Integer> map = getSumOfGenres(genres, plays);
        Album[] albums = getAlbums(genres, plays, map);

        // 1) 재생 노래 횟수가 같을경우 => 고유 번호가 낮은 순으로 오름차순
        // 2) 재생된 장르 수가 같을경우 => 재생 노래 횟수 순 내림차순
        // * 재생된 장르 수(오름차순) -> 장르 내에서 재생된 노래 횟수(오름차순) -> 노래 별 고유 번호(내림차순)
        Arrays.sort(albums, (i1, i2) -> {
            if (i2.sum == i1.sum) {
                if (i2.plays == i1.plays) {
                    return Integer.compare(i1.index, i2.index);
                }
                return Integer.compare(i2.plays, i1.plays);
            }
            return Integer.compare(i2.sum, i1.sum);
        });

        for (int i = 0; i < length; i++) {
            System.out.println(albums[i].toString());
        }

        int count = 1;
        list.add(albums[0].index);
        for (int i = 1; i < length; i++) {
            if (count == 2 && albums[i].genres.equals(albums[i - 1].genres)) {
                continue;
            }
            if (!albums[i].genres.equals(albums[i - 1].genres)) {
                count = 0;
            }

            list.add(albums[i].index);
            count ++;
        }
        return list.stream().mapToInt(Integer::intValue).toArray();
    }

    private static Album[] getAlbums(String[] genres, int[] plays, Map<String, Integer> map) {
        Album[] albums = new Album[genres.length];

        for (int i = 0; i < genres.length; i++) {
            Album album = new Album(genres[i], plays[i], map.get(genres[i]), i);
            albums[i] = album;
        }
        return albums;
    }

    private static Map<String, Integer> getSumOfGenres(String[] genres, int[] plays) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < genres.length; i++) {
            map.put(genres[i], map.getOrDefault(genres[i], 0) + plays[i]);
        }
        return map;
    }

    static class Album {
        String genres;
        int plays;
        int sum;
        int index;

        private Album() {
        }

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

        @Override
        public String toString() {
            return "Album{" +
                    "genres='" + genres + '\'' +
                    ", plays=" + plays +
                    ", sum=" + sum +
                    ", index=" + index +
                    '}';
        }
    }

    public static void main(String[] args) {
        String[] genres = {"c", "a", "b", "a", "a", "b", "b", "b", "b", "c", "c", "c", "d"};
        int[] plays = {1, 500, 9, 600, 501, 800, 500, 300, 2, 2, 1, 2, 100000};

        int[] result = solution(genres, plays);
        System.out.println(Arrays.toString(result));
    }
}

 

 

풀이

문제에서 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 라고 명시되어 있는 부분이 이 문제의 핵심입니다.

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

 

위 기준에 따라 적당히 정렬 조건을 명시하면서 문제를 해결해나가면 될 것 같습니다.

 

저는 아래와 같이 정렬을 기대하고 문제를 접근했는데요,

 

1) 속한 노래가 많이 재생된 장르(sum)를 먼저 수록합니다. (내림차순)

• 각 장르별 총 재생된 횟수를 구합니다.

 

2) 장르(genres) 내에서 많이 재생된 노래(plays)를 먼저 수록합니다. (내림차순)

• 1)에서 조건이 동일할 경우, 많이 재생된 노래 순으로 정렬을 합니다.

 

3) 장르 내에서 재생 횟수(plays)가 같은 노래 중에서는 고유 번호(index)가 낮은 노래를 먼저 수록합니다. (오름차순)

• 1)이 동일하고, 2)이 동일할 경우 -> 고유 번호(index)가 낮은 노래 순으로 정렬을 합니다.

 

 

따라서 장르명과 위 3가지를 필드로 가지는 Album 클래스를 inner class로 생성합니다.

    static class Album {
        String genres;
        int plays;
        int sum;
        int index;

        private Album() {
        }

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

 

아래와 같이 정렬을 Album에서 Comparable을 implements 한 뒤 구현해도 되지만, 저는 익명 클래스로 구현을 했습니다.

static class Album implements Comparable<Album> {
    ...
    
    @Override
    public int compareTo(Album o) {
        if (o.sum == this.sum) {
            if (o.plays == this.plays) {
                return Integer.compare(this.index, o.index);
            }
            return Integer.compare(o.plays, this.plays);
        }
        return Integer.compare(o.sum, this.sum);
    }
}

 

 

그 후 위에서 설명드린 1) ~ 3) 풀이에 대해 간략히 살펴보겠습니다.

 

 

1) 속한 노래가 많이 재생된 장르를 먼저 수록합니다. (내림차순)

• 각 장르별 총 재생된 횟수를 구합니다.

저는 Map<String, Integer>으로 장르명과 장르별 총 재생된 횟수를 계산했습니다.

    Map<String, Integer> map = getSumOfGenres(genres, plays);

    private static Map<String, Integer> getSumOfGenres(String[] genres, int[] plays) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < genres.length; i++) {
            map.put(genres[i], map.getOrDefault(genres[i], 0) + plays[i]);
        }
        return map;
    }

 

 

 

2) 장르 내에서 많이 재생된 노래를 먼저 수록합니다. (내림차순)

• 1)에서 조건이 동일할 경우, 많이 재생된 노래 순으로 정렬을 합니다.

 

3) 장르 내에서 재생 횟수가 같은 노래 중에서는 고유 번호가 낮은 노래를 먼저 수록합니다. (오름차순)

• 1)이 동일하고, 2)이 동일할 경우 -> 고유 번호(index)가 낮은 노래 순으로 정렬을 합니다.

위 문제에 대한 정렬은 다음과 같습니다.

        // 1) 재생 노래 횟수가 같을경우 => 고유 번호가 낮은 순으로 오름차순
        // 2) 재생된 장르 수가 같을경우 => 재생 노래 횟수 순 내림차순
        // * 재생된 장르 수(오름차순) -> 장르 내에서 재생된 노래 횟수(오름차순) -> 노래 별 고유 번호(내림차순)
        Arrays.sort(albums, (i1, i2) -> {
            if (i2.sum == i1.sum) {
                if (i2.plays == i1.plays) {
                    return Integer.compare(i1.index, i2.index);
                }
                return Integer.compare(i2.plays, i1.plays);
            }
            return Integer.compare(i2.sum, i1.sum);
        });

 

 

마지막으로 노래는 두 개씩 모아 베스트 앨범을 출시하기 때문에 다음과 같이 구현을 했습니다.

        for (int i = 1; i < length; i++) {
            if (count == 2 && albums[i].genres.equals(albums[i - 1].genres)) {
                continue;
            }
            if (!albums[i].genres.equals(albums[i - 1].genres)) {
                count = 0;
            }

            list.add(albums[i].index);
            count ++;
        }

장르는 최대 2개만 출시를 해야하기 때문에, 전에 출시한 장르와 비교를 합니다.

 

만약, 2개를 출시했고 다음 출시하려는 장르가 이전에 출시한 장르와 동일할 경우

• 이 경우 더이상 출시를 하지 않고 for문을 건너뜁니다(continue)
• ex) 'pop', 'pop', 'pop', 'pop' 

 

만약 이전에 출시한 장르와 현재 출시한 장르가 다를 경우

• 현재 출시하려는 장르를 0으로 초기화합니다.