[프로그래머스] 2023 KAKAO BLIND RECRUITMENT 이모티콘 할인 행사 코틀린 풀이

 

오늘은 카카오의 코딩테스트 기출 이모티콘 할인 행사 문제를 풀어보려고 한다.

난이도 Lv.2라 쉽게 봤는데 생각보다 빡셌다.

(체감상 Lv.3에 가까운 Lv.2가 아닌가 싶다.)

 

---

📝 문제 간단 요약

이 문제는 다음과 같은 상황을 다룬다.

• 카카오톡에서 이모티콘 플러스 가입자를 늘리고 싶어 한다.
• 이모티콘마다 10%, 20%, 30%, 40% 할인율 중 하나를 선택해 판매할 수 있다.
• 유저는
  • 최소 몇 % 이상 할인해야 살지 결정한다.
  • 살 이모티콘 총합 금액이 일정 기준을 넘으면 구매를 취소하고 플러스 서비스에 가입한다.

목표는 두 가지다.

1. 가입자 수를 최대로 만든다.
2. 가입자 수가 같다면 매출을 최대로 만든다.

 

---

 

🤔 어떻게 접근할까?

문제를 처음 보면 어떻게 할인율을 정해야 하나? 라는 고민이 든다.
하지만 할인율이 4가지 뿐이므로 경우의 수가 생각보다 적다.

• 할인율은 4가지다.
• 이모티콘이 m개라면 → 경우의 수는 4^m 개다.

예를 들어 이모티콘이 2개라면 4^2 = 16 가지 조합만 살펴보면 된다.
따라서 완전탐색으로 충분히 풀 수 있다.

 

 

---

 

✅ 풀이 계획

다음과 같은 순서로 풀어보자.

1. 이모티콘마다 할인율을 정한다. (10%, 20%, 30%, 40%)
2. 모든 할인 조합을 완전탐색한다.
3. 각 조합에 대해 모든 유저를 검사한다.
   • 할인율 기준 이상인 이모티콘만 구매한다.
   • 이모티콘 총합이 기준 이상이면 가입한다.
   • 아니면 매출에 포함한다.
4. 최종적으로 가입자 수와 매출을 비교해 최대값을 선택한다.

 

---

 

💡 왜 완전탐색으로 풀 수 있을까?

최대 이모티콘 개수는 7개다.

-> 4^7 = 16384

약 16,000번의 탐색으로 충분히 풀 수 있으므로 완전탐색으로 풀자.

 

---

✨ 구현 방법

먼저 할인율 배열을 만든다.

val discountRates = listOf(10, 20, 30, 40)

 

---

 

▶ 모든 할인율 조합 만들기

이모티콘이 2개라면:

• (10%, 10%)
• (10%, 20%)
• ...
• (40%, 40%)

이렇게 4진수 순열을 만들어야 한다.
이를 DFS로 구현하자.

 

val emoticons = listOf(7000, 9000)
val emoticonCount = emoticons.size

val allDiscountsChosen = mutableListOf<List<Int>>()

fun dfs(depth: Int, path: MutableList<Int>) {
    if (depth == emoticonCount) {
        allDiscountsChosen.add(path.toList())
        return
    }
    for (i in 0 until 4) {
        path.add(i)
        dfs(depth + 1, path)
        path.removeAt(path.size - 1)
    }
}

dfs(0, mutableListOf())

 

이렇게 하면 모든 할인율 조합이 구해진다.

 

 

---

 

▶ 각 조합마다 유저를 검사하자

예를 들어 discountsChosen = [2, 3]이면

• 이모티콘1 → discountRates[2] = 30%
• 이모티콘2 → discountRates[3] = 40%

각 유저별로

• 자신의 할인 기준 이상인 이모티콘만 고른다.
• 가격을 합산한다.
• 금액이 기준을 넘으면 가입한다.
• 아니면 매출에 더한다.

 

 

 

---

 

▶ 실행 예시

테스트 데이터를 넣어 실행해보자.

fun main() {
    val users = listOf(
        listOf(40, 10000),
        listOf(25, 10000)
    )
    val emoticons = listOf(7000, 9000)

    val result = solution(users, emoticons)
    println(result.contentToString())
}

 

 

출력 결과는 아래와 같다.

[1, 5400]

 

 

---

▶ 최종 코드(제출용)

class Solution {
    fun solution(users: Array<IntArray>, emoticons: IntArray): IntArray {
        val discountRates = listOf(10, 20, 30, 40)
        val emoticonCount = emoticons.size

        val allDiscountsChosen = mutableListOf<List<Int>>()

        fun dfs(depth: Int, path: MutableList<Int>) {
            if (depth == emoticonCount) {
                allDiscountsChosen.add(path.toList())
                return
            }
            for (i in 0 until 4) {
                path.add(i)
                dfs(depth + 1, path)
                path.removeAt(path.size - 1)
            }
        }

        dfs(0, mutableListOf())

        var maxSubscribers = 0
        var maxRevenue = 0

        for (discountsChosen in allDiscountsChosen) {
            var subscribers = 0
            var revenue = 0

            for (user in users) {
                val userDiscountLimit = user[0]
                val userPriceLimit = user[1]

                var total = 0

                for (i in emoticons.indices) {
                    val discountPercent = discountRates[discountsChosen[i]]
                    if (discountPercent >= userDiscountLimit) {
                        val discountedPrice = emoticons[i] * (100 - discountPercent) / 100
                        total += discountedPrice
                    }
                }

                if (total >= userPriceLimit) {
                    subscribers += 1
                } else {
                    revenue += total
                }
            }

            if (subscribers > maxSubscribers) {
                maxSubscribers = subscribers
                maxRevenue = revenue
            } else if (subscribers == maxSubscribers && revenue > maxRevenue) {
                maxRevenue = revenue
            }
        }

        return intArrayOf(maxSubscribers, maxRevenue)
    }
}

 

 

⏱️ 시간 복잡도

• 이모티콘 개수 m ≤ 7
• 할인율 조합 수 4^m
• 유저 수 ≤ 100명

완전탐색으로 충분히 풀 수 있는 문제다.

 

---

 

✨ 핵심 포인트

• 제한된 선택지(할인율)는 완전탐색으로 해결하자.
• 유저별 할인 기준을 정확히 비교하자.
• 가입자 수를 최우선으로 비교하고, 같으면 매출을 비교하자.

이것이 이 문제의 핵심이다.

 

 

---

 

 

 

 

이 문제의 핵심인 DFS 알고리즘에 대해 잘 모르는 사람은 아래의 포스팅을 참고하자.

=> DFS/BFS 알고리즘이란?

 

---

 

마무리

처음 보면 헷갈릴 수 있는 문제이지만, 할인율 배정 → 유저별 시뮬레이션만 반복하면 풀리는 문제다.