알고리즘 8편 Hash 난이도3 베스트앨범 lamda 함수형 코틀린(kotlin) 으로 시작하는 문제해결방법

안녕하세요

앵과장입니다.

 

베스트 앨범 Hash 난이도 3

문제 설명

스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다.

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

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

제한사항

• genres [i]는 고유번호가 i인 노래의 장르입니다.
• plays [i]는 고유번호가 i인 노래가 재생된 횟수입니다.
• genres와 plays의 길이는 같으며, 이는 1 이상 10,000 이하입니다.
• 장르 종류는 100개 미만입니다.
• 장르에 속한 곡이 하나라면, 하나의 곡만 선택합니다.
• 모든 장르는 재생된 횟수가 다릅니다.

입출력 예

genresplaysreturn

["classic", "pop", "classic", "classic", "pop"]

[500, 600, 150, 800, 2500]

[4, 1, 3, 0]

입출력 예 설명

classic 장르는 1,450회 재생되었으며, classic 노래는 다음과 같습니다.

• 고유 번호 3: 800회 재생
• 고유 번호 0: 500회 재생
• 고유 번호 2: 150회 재생

pop 장르는 3,100회 재생되었으며, pop 노래는 다음과 같습니다.

• 고유 번호 4: 2,500회 재생
• 고유 번호 1: 600회 재생

따라서 pop 장르의 [4, 1]번 노래를 먼저, classic 장르의 [3, 0]번 노래를 그다음에 수록합니다.

 

 

난이도 3인만큼이나 간단할 것 같지만 고민하면서 풀 수밖에 없는 형태입니다.

 

class Solution {
     fun solution(genres: Array<String>, plays: IntArray): IntArray {
        var answer = intArrayOf()

        // 장르별 재생 횟수 맵 구현
        // playsMap["classic"] = 1000
        // playsMap["pop"] = 2100
        var playsMap = mutableMapOf<String, Int>()
        genres.forEachIndexed { index, element ->
            playsMap.put(
                    element,
                    playsMap.getOrDefault(element, 0) + plays[index]
            )
        }

        val topGenres = playsMap.toList()
                .sortedByDescending { (_, value) -> value}
                .toMap()
                .keys


        var topRank = mutableMapOf<String, IntArray>()
        playsMap.forEach {
            topRank.put(it.key, intArrayOf(-1, -1))
        }

        genres.forEachIndexed { index, element ->
            if (topRank[element]!![0] == -1 ||
                    plays[topRank[element]!![0]] < plays[index]) {
                topRank[element]!![1] = topRank[element]!![0]
                topRank[element]!![0] = index
            } else if (topRank[element]!![1] == -1 ||
                    plays[topRank[element]!![1]] < plays[index]) {
                topRank[element]!![1] = index
            }
        }


        topGenres.forEach {
            if (topRank[it]!![0] != -1) {
                answer = answer.plus(topRank[it]!![0])
            }

            if (topRank[it]!![1] != -1) {
                answer = answer.plus(topRank[it]!![1])
            }
        }

        return answer
    }
}

// 장르별 재생 횟수 맵 구현
// playsMap["classic"] = 1000
// playsMap["pop"] = 2100

// topRank map 구현
// topRank = foreach(playsMap)


// 장르별 최대 재생 횟수 음악 설정
// topRank["classic"][0] = 1
// topRank["classic"][1] = 5

 

함수형에 대한 인지가 되어있는 상태라면 아주 심플하게 나올 수도 있는데요

class Solution {
    fun solution(genres: Array<String>, plays: IntArray): IntArray {
        return genres.indices.groupBy { genres[it] }
            .toList()
            .sortedByDescending { it.second.sumBy { plays[it] } }
            .map { it.second.sortedByDescending { plays[it] }.take(2) }
            .flatten()
            .toIntArray()
    }
}

 

 

it ?이란

 

네 가지 모두 같은 표현입니다.

people.maxBy ({p: Person -> p.age})
people.maxBy () {p: Person -> p.age}
people.maxBy {p: Person -> p.age}
people.maxBy {it.age}

 

• 함수의 맨 마지막 인자가 람다라면 () 안에서 빼내서 밖에 람다를 표현할 수 있다.
• 인자가 하나라면 그 인자는 람다식 내부에서 it으로 받을 수 있다.
• 인자가 하나이면서 그 인자가 람다 타입이라면 ()를 생략할 수 있다.

 

 

sortedByDescending

정렬 함수중 하나입니다.

이해를 돕기 위해서 아래 사용되는 것들도 추가합니다.

 

오름차순 : sortedBy

내림차순 : sortedByDescending

역정렬 : reversed

랜덤정렬 : shuffled

 

data class Person(val name:String, val age:Int)

    @Test
    fun 코틀린정렬(){
        var list = listOf(2,1,3,4)

        var list1 = list.reversed() // 순서 반대로
        var list2 = list.sorted() // 오름차순 정렬
        var list3 = list.sortedDescending() // 내림차순 정렬
        var list4 = list.shuffled() // 랜덤 정렬

        list1.forEach(){print("$it ")}
        println()
        list2.forEach(){print("$it ")}
        println()
        list3.forEach(){print("$it ")}
        println()
        list4.forEach(){print("$it ")}
        println()

        var personList = listOf(
            Person("Han",25),
            Person("Kim",19),
            Person("Lee",27),
            Person("Choi",25)
        )

        var personList1 = personList.sortedBy {it.age } // 조건부 오름차순 정렬
        var personList2 = personList.sortedByDescending {it.age } // 조건부 내림차순 정렬
        var personList3 = personList.sortedWith(compareBy({ it.age }, { it.name })) // 여러 조건으로 정렬
        // 클래스배열이 아닌 그냥 배열이면 it.first... 등으로 요소 접근

        personList1.forEach(){print("$it ")}
        println()
        personList2.forEach(){print("$it ")}
        println()
        personList3.forEach(){print("$it ")}
        println()

    }

 

flatten

2개의 배열을 한 개의 배열로 플랫 하게 펼치는 방법입니다.

여러 배열들을 1개로 펴야 할 때 사용합니다.

 

아래 형태 2차원 배열에 2번째 값만 아래 2번째 처럼해야할때

 

[([pop], [1, 4]), ([classic], [0, 2, 3])]

[4, 1, 3, 0] 

        println(mapToPairList.sortedByDescending { it.second.sumOf { plays[it] } }
            .map { it.second.sortedByDescending { plays[it] }.take(2) }.flatten())

it.second 는 List<Pair<List<String>, List<Int>> 이형태일 때 

Pair는 첫 번째 List<String>, 두번째 List<Int> 를 first, second 로 접근해서 가져올 수 있습니다.

이번에 베스트 앨범에서는 해당 index값으로 plays 된 횟수를 가져와야 하기 때문에 index배열인 2번째를 가져오려고 second를 사용합니다.

 

.toList()

.toIntArray()

나머지 2개는 type을 변환합니다. 이건 Java에서도 많이 사용하였고

to 라는 연결자로 이름을 많이 만드는데 특정한 타입을 원하는 타입으로 사용할때 주로 사용합니다.

 

오늘 이해가 되셨나요

함수형 프로그래밍은 강력하지만 잘 알고 사용해야 한다는 점 그리고 코틀린에서

제공하는 여러 함수들을 하나씩 재미있게 배우면 기존에 소스보다 손쉽게 프로그래밍을 할 수 있는 점 기억하세요

 

베스트 앨범으로 이달의 소녀를 추천합니다.+_+ 좋아요