【프로그래머스】 이모티콘 할인행사 (Kotlin)

문제

프로그래머스

 

풀이

이모티콘마다 다른 할인율을 적용했을 때 플러스 서비스 가입자 수 및 이모티콘 구매 금액을 IntArray에 담고 이를 최대 힙에 추가한다.

모든 경우에 대한 결과를 힙에 추가했다면 peek한 IntArray를 정답으로 리턴한다.

 

최대 힙 준비하기

IntArray를 담을 새 PriorityQueue 객체를 생성한다.

각 IntArray의 첫 번째 원소는 플러스 서비스 가입자 수이고 두 번째 원소는 이모티콘 판매액이다.

문제에서 제시한 목표에 따라 Comparator를 설정한다.

// 서비스 가입자 수에 대해 내림차순으로 정렬한다.
// 가입자 수가 같다면 판매액에 대해 내림차순으로 정렬한다.
val comparator = compareByDescending<IntArray> { it[0] }
    .thenByDescending { it[1] }
    
// Comparator를 적용한 새 힙 객체를 생성한다.
val resultHeap = PriorityQueue(comparator)

 

깊이 우선 탐색(DFS)하기

재귀함수로 인덱스를 증가시키며 각 이모티콘에 적용할 할인율을 선택하여 DFS를 진행한다. 

이 때 각 이모티콘에 적용할 할인율을 기억하기 위해 emoticons와 크기가 같은 IntArray를 사용한다.

 

마지막 이모티콘까지 할인율을 지정한 뒤 이를 적용했을 때 서비스 가입자 수 및 이모티콘 판매액을 구한다.

이 데이터를 포함하는 IntArray를 힙에 추가한 다음 리턴하여 다음 단계를 진행한다.

val rates = IntArray(emoticons.size)

fun dfs(depth: Int) {
    
    // 모든 이모티콘에 할인율을 지정한 뒤
    if (depth == emoticons.size) {
    
        // 힙에 결과 배열을 추가한 다음 리턴한다.
        resultHeap.offer(getResult())
        return
    }
    
    // 적용할 수 있는 할인율은 10, 20, 30, 40 퍼센트다.
    for (rate in 10..40 step 10) {
        
        // depth(인덱스)에 해당하는 할인율을 저장하고 다음 단계로 진행한다.
        rates[depth] = rate
        dfs(depth + 1)
    }
}

 

결과 배열 생성하기

이모티콘마다 지정한 각 할인율을 적용하여 서비스 구독자 수 및 총 판매액을 계산하여 IntArray에 저장한다.

fun getResult(): IntArray {

    // 첫 번째 원소는 서비스 가입자 수, 두 번째 원소는 이모티콘 판매액이다.
    val result = intArrayOf(0, 0)
    
    userLoop@ for (user in users) {
    
        // 사용자의 이모티콘 구매액
        var amount = 0
        for (i in emoticons.indices) {
        
            // 할인율이 사용자의 기준 할인율 이상인 경우
            if (rates[i] >= user[0]) {
            
                // 구매액에 이모티콘의 할인가를 합산한다.
                amount += emoticons[i] * (100 - rates[i]) / 100
                
                // 합산할 때마다 구매액이 기준 비용 이상인지 체크한다.
                // 기준 비용 이상이라면 서비스 가입자로 처리하고 바로 다음 사용자로 넘어간다.
                if (amount >= user[1]) {
                    result[0]++
                    continue@userLoop
                }
            }
        }
        
        // 사용자의 구매액을 판매액에 합산한다.
        result[1] += amount
    }
    return result
}

 

코드

GitHub - blacksg/ProblemSolving

import java.util.PriorityQueue

class Solution {
    fun solution(users: Array<IntArray>, emoticons: IntArray): IntArray {
        val rates = IntArray(emoticons.size)
        val resultHeap = PriorityQueue(compareByDescending<IntArray> { it[0] }
            .thenByDescending { it[1] })
        
        fun getResult(): IntArray {
            val result = intArrayOf(0, 0)
            userLoop@ for (user in users) {
                var amount = 0
                for (i in emoticons.indices) {
                    if (rates[i] >= user[0]) {
                        amount += emoticons[i] * (100 - rates[i]) / 100
                        if (amount >= user[1]) {
                            result[0]++
                            continue@userLoop
                        }
                    }
                }
                result[1] += amount
            }
            return result
        }
        
        fun dfs(depth: Int) {
            if (depth == emoticons.size) {
                resultHeap.offer(getResult())
                return
            }
            for (rate in 10..40 step 10) {
                rates[depth] = rate
                dfs(depth + 1)
            }
        }
        
        dfs(0)
        return resultHeap.peek()
    }
}