[프로그래머스] 2023 KAKAO BLIND RECRUITMENT 이모티콘 할인행사 with Kotlin

문제

이모티콘 할인율: 10%, 20%, 30%, 40%

유저는 본인이 정한 할인율 이상일 경우에 무조건 이모티콘을 구매한다.

이 때, 구매한 이모티콘 가격이 유저가 정해놓은 가격 이상일 경우 >> 구매했던 이모티콘을 모두 취소하고 카카오 이모티콘 플러스를 구매한다.

 

이모티콘별로 할인율을 적절히 선택하여 최적의 결과를 도출하여라

• 결과 -> [이모티콘 플러스 가입 수 , 이모티콘 총 구매 가격]
• 우선순위는 1번이 이모티콘 플러스 가입 수, 2번이 이모티콘 총 구매 가격
• users: [본인이 정한 할인율, 본인이 정한 가격]

입출력 예

users	emoticons	result
[[40, 10000], [25, 10000]]	[7000, 9000]	[1, 5400]
[[40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900]]	[1300, 1500, 1600, 4900]	[4, 13860]

 

풀이 과정

• 이모티콘 별로 할인율을 전부 대입하여 최선의 결과를 선택하는 완전 탐색 문제로 예상 -> DFS
• 이모티콘 구입 조건에 맞을 경우 할인을 적용한 이모티콘 가격을 유저별 이모티콘 구매 배열에 저장
• 마지막 이모티콘까지 끝났다면, 각 유저별 구매 금액과 정해놓은 금액 비교 후 result 생성
• 우선순위를 비교하여 적합한 result를 answer에 저장 후 재귀함수 종료

 

코드

class Solution {
    // 할인율 : 10%, 20%, 30%, 40%
    // 할인율을 전부 대입하고 최선의 결과를 선택하는 완전 탐색 문제로 예상 -> DFS
    val discount = arrayOf(0.4, 0.3, 0.2, 0.1)
    var answer: IntArray = intArrayOf(0, 0)
    fun solution(users: Array<IntArray>, emoticons: IntArray): IntArray {
        
        Dfs(users, emoticons, 0, Array(users.size, {0}))
        
        return answer
    }
    
    // index : 이모티콘 인덱스 
    fun Dfs(users: Array<IntArray>, emoticons: IntArray, index: Int, temp: Array<Int>){
        // temp 정리 저장 후 종료
        if(index >= emoticons.size) {
            val result = intArrayOf(0, 0)
            
            for(i in temp.indices){
                if(temp[i] >= users[i][1]) result[0]++ // 구매 비용이 오바했다면
                else result[1] += temp[i] // 오바 안했다면
            }
            
            // answer가 비어있다면
            if(answer == intArrayOf(0, 0)) answer = result
            // 비어있지 않다면
            else{
                if(answer[0] < result[0]) answer = result // 이모티콘 플러스 기준
                
                else if(answer[0] == result[0]){ // 이모티콘 플로스가 같은 때 구매 비용 기준
                    answer[1] = Math.max(answer[1], result[1])
                }
            }
            
            return
        }
        
        for(i in discount){
            // 유저 별 이모티콘 구매 가격 저장
            val save = temp.copyOf()
            
            // 가격 계산 후 save에 저장
            for(j in users.indices){
                if(i*100 >= users[j][0]){
                    val price = emoticons[index] - (emoticons[index] * i).toInt()
                    save[j] += price
                }
            }
            
            Dfs(users, emoticons, index+1, save)
        }
    }
}