[Kotlin, Lv.3] 프로그래머스 베스트앨범

출처: unsplash.com

 

베스트앨범

Level 3

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

 

문제 내용

 

 

문제 접근

가장 많이 재생된 노래를 장르별로 2개씩 모아서 각 노래의 고유 번호를 순서대로 출력해야 한다.

문제의 예제를 표로 그려보면 다음과 같다.

사진 1-1

입력된 순서대로 고유 번호가 주어진다.

그리고 노래의 장르와 재생 횟수가 같이 주어진다. 장르와 재생 횟수는 고유 번호가 동일한 것끼리가 한 노래의 통계가 될 것이다.

 

문제에서 요구한 조건대로 우선적으로 정렬해 준 다음 고유 번호를 출력하자.

1. 가장 많이 재생된 장르

2. 장르 내에서 가장 많이 재생된 노래

3. 장르 내에서 재생 횟수가 같으면 고유 번호가 작은 노래

위 조건들을 순서대로 적용시켜서 순서를 변경시키면 아래와 같다.

사진 1-2

가장 재생 횟수가 많은 pop(3100)을 가장 상단에 배치한다.

그다음 pop 노래 중 가장 재생 횟수가 많은 순서대로 정렬해 준다.

다른 장르들의 노래도 같은 방법으로 정렬해 주면 사진 1-2처럼 될 것이다.

하지만 베스트앨범에 등재되기 위해서는 장르에서 노래 2개씩을 뽑아야 하기 때문에 가장 순서가 밀리는 classic의 2번 노래를 제외하고 노래의 고유 번호를 출력한다.

그러면 4, 1, 3, 0이 될 것이다.

 

코드로 구현하기 위해서는 우선 장르별 총 재생 횟수를 담을 Map을 생성해서 각 노래의 재생 횟수가 들어오면 각 장르에 맞게 값을 추가해 줘야 한다.

// 키가 없는 경우
musicPlay[genresType] = play
// 키가 있는 경우
musicPlay[genresType] = musicPlay[genresType]!! + play

키가 없으면 초기값을 play로 새롭게 데이터를 만들어 주고, 키가 있으면 기존 데이터에 play를 더해 준다.

 

그리고 노래의 장르, 고유 번호. 재생 횟수를 담을 Map을 만들어서 key를 장르로 잡고, value를 하위 Map을 구성해 key를 고유 번호, value를 재생 횟수를 담아 준다.

 

또한 한 장르에 노래가 최대 2개까지 수록되어야 하기 때문에, 이미 2개가 저장되어 있으면 재생 횟수가 최솟값이 값의 key를 구해서 최솟값보다 현재 노래의 재생 횟수가 큰지 확인한다.

Map에서 최솟값은 다음과 같이 구할 수 있다.

val minPlays = music[genresType]!!.minOf { it.value }

이 최솟값과 현재 재생 횟수를 비교하는 조건은 minPlays < play이다.

 

다음으로는 장르별로 재생 횟수가 많은 순서대로 정렬해주어야 한다.

노래 재생 횟수가 큰 순서대로 정렬해 주는 방법은 Kotlin에서는 아래와 같이 사용할 수 있다.

Map에서 정렬은 LinkedList에 Map.entries에 넣고 sort 함수를 수행해 주면 된다.

val musicPlayEntries = LinkedList(musicPlay.entries)
musicPlayEntries.sortByDescending { it.value }

 

정렬된 장르값을 key로 받는 map의 재생 횟수(value)들끼리 큰 순서대로 정렬을 해주고, 정렬 결과의 key를 불러오면 정답이 된다.

 

 

 

문제 해결 코드

fun solution(genres: Array<String>, plays: IntArray): IntArray {
    val answer = mutableListOf<Int>()
    val music = mutableMapOf<String, MutableMap<Int, Int>>()
    val musicPlay = mutableMapOf<String, Int>() // 총 재생 횟수

    for (i in genres.indices) {
        val genresType = genres[i]
        val play = plays[i]

        if (!music.containsKey(genresType)) {
            music[genresType] = mutableMapOf(i to play)
            musicPlay[genresType] = play
        } else {
            musicPlay[genresType] = musicPlay[genresType]!! + play

            if (music[genresType]!!.size < 2) {
                music[genresType]?.set(i, play)
            } else {
                val minPlays = music[genresType]!!.minOf { it.value }
                if (minPlays < play) {
                    val minIndex = music[genresType]!!.values.indexOf(minPlays)
                    val minKey = music[genresType]!!.keys.toList()[minIndex]

                    music[genresType]?.remove(minKey)
                    music[genresType]?.set(i, play)
                }
            }
        }
    }

    val musicPlayEntries = LinkedList(musicPlay.entries)
    musicPlayEntries.sortByDescending { it.value }

    for (i in 0 until musicPlayEntries.size) {
        val key = musicPlayEntries[i].key
        val musicInfo = LinkedList(music[key]!!.entries)

        musicInfo.sortByDescending { it.value }
        for (m in musicInfo) {
            answer.add(m.key)
        }
    }

    return answer.toIntArray()
}

 

문제 풀이

노래의 장르, 고유 번호, 재생 횟수를 저장할 map(music)과 노래의 장르와 총 재생 횟수를 저장할 map(musicPlay)을 생성하고

처음에 map들이 비어 있을 때는 key를 genresType으로 설정해 초기화해 준다.

map에 key 값이 들어 있으면, 최댓값 map은 값을 계속 장르마다 더해주면 되고,

music의 경우에는 저장된 노래의 개수가 2개를 넘으면 안 되기 때문에 현재 재생 횟수의 최솟값을 찾아 해당 값의 key를 찾아 준다.

val minPlays = music[genresType]!!.minOf { it.value }

최솟값이 현재 재생 횟수보다 작은 경우에만 수행해 준다.

최솟값이 들어 있는 index를 찾게 되면, map의 key들이 있는 list에서 index에 해당되는 key의 값이 삭제해야 할 key가 된다.

val minIndex = music[genresType]!!.values.indexOf(minPlays)
val minKey = music[genresType]!!.keys.toList()[minIndex]

music[genresType]?.remove(minKey)
music[genresType]?.set(i, play)

 

마지막에는 정렬을 해주어야 한다.

우선 정렬하려고 하는 map을 LinkedList로 받아 주고, 총 재생 횟수 순으로 값을 정렬한다.

다음 musicPlay의 key(장르)를 music에 이용해 하위 map도 정렬을 해준다.

정렬된 결과에서 key를 answer에 추가해 준다.

 

 

문제 해결 과정

map을 이용하면 쉽게 해결할 수 있다.

나의 경우에는 총 재생 횟수와 장르별 노래를 각각의 map으로 생성해서 구현했는데, 하나로 했으면 상당히 map이 복잡해졌을 것 같다.

map에서 key와 value 참조 및 map에서의 정렬을 연습해 볼 수 있는 문제였다.