프로그래머스 이모티콘 할인행사 Python

프로그래머스 이모티콘 할인행사 python

문제

📌 문제 설명

카카오톡에서는 ‘이모티콘 플러스’라는 구독형 서비스를 운영 중이며, 이 서비스를 보다 많은 사용자에게 가입시키고자 이모티콘 할인 행사를 진행합니다.

이 할인 행사는 다음 두 가지 목표를 가지고 있습니다.

1순위 목표: 이모티콘 플러스 서비스의 가입자를 최대한 많이 확보하는 것
2순위 목표: 이모티콘 판매로 얻는 매출을 최대한 많이 올리는 것

즉, 구독자가 늘어난다면 수익이 조금 낮더라도 괜찮지만, 구독자 수가 같다면 그 중 수익이 더 높은 쪽을 선택해야 합니다.

👤 사용자 정보

사용자는 각자 다음과 같은 기준 두 가지를 갖고 있습니다.

• 할인 기준 % : 본인이 설정한 할인률 이상일 경우에만 해당 이모티콘을 구매합니다.
• 가격 기준 원 : 할인된 이모티콘 가격을 모두 합한 금액이 이 기준 이상이면, 이모티콘 구매를 취소하고 구독 서비스에 가입합니다.

즉, 사용자는 아래 두 가지 조건에 따라 행동합니다.

할인률이 기준 이상인 이모티콘만 선택하고,
그 이모티콘들의 합계가 가격 기준 이상이면 전부 구매를 취소하고 구독으로 전환함

📦 이모티콘 정보

• 이모티콘은 각기 다른 정가를 가지며, 할인률은 다음 중 하나로 정해집니다:
  10%, 20%, 30%, 40%
• 이 할인률은 이모티콘마다 개별적으로 정할 수 있으며, 전체 이모티콘에 대해 모든 할인 조합을 시도해봐야 합니다.

✅ 입력 조건 요약

항목	설명
users	각 사용자 [할인기준 %, 가격기준]을 담은 배열
emoticons	각 이모티콘의 정가를 담은 배열
반환값	[가입자 수, 이모티콘 판매 수익] 리스트

🧪 테스트케이스 예시

예시 1:

• users = [[40, 10000], [25, 10000]]
• emoticons = [7000, 9000]
• return = [1, 5400]

예시 2:

• users = [[40, 2900], [23, 10000], [11, 5200], [5, 5900], [40, 3100], [27, 9200], [32, 6900]]
• emoticons = [1300, 1500, 1600, 4900]
• return = [4, 13860]

⚙️ 문제 작동 원리

1. 이모티콘마다 가능한 모든 할인율 조합을 구합니다.
   이모티콘이 N개일 때 가능한 할인 조합 수는 4^N입니다.
2. 각 할인율 조합에 대해 모든 사용자에 대해 다음을 반복합니다:
• 할인률 조건을 만족하는 이모티콘만 선택하여 총합 계산
• 총합이 기준 가격 이상이면 → 구독자로 전환
• 총합이 기준 가격 미만이면 → 해당 금액만큼 판매 수익
3. 이 모든 조합을 비교하여,
• 구독자 수가 최대인 조합을 우선 선택
• 구독자 수가 동일할 경우 판매 수익이 더 높은 조합 선택

아이디어

✅ 접근 방식 요약

• 모든 할인율 조합을 DFS(깊이 우선 탐색)으로 생성합니다.
• 조합이 완성될 때마다 모든 사용자에 대해 구독/구매 판단을 수행합니다.
• 가입자 수가 많은 조합을 우선 저장하고, 동일하면 수익이 높은 쪽으로 갱신합니다.

🧭 DFS의 구조

할인율 조합을 트리 형태로 생각해 볼 수 있습니다.
예를 들어 이모티콘이 2개라면 다음과 같은 트리 구조가 됩니다.

                (start)
               /   |   |   \
           10% 20% 30% 40%
           /|\   /|\   /|\   /|\
        ... 반복 ... 깊이 = 이모티콘 수

즉, 깊이가 이모티콘의 개수이며, 각 깊이마다 4가지 분기를 생성합니다.
깊이가 이모티콘 개수에 도달하면 해당 할인 조합을 완성한 것입니다.

✅ 사용자 평가 방식

할인 조합이 하나 완성되면, 이제 사용자 정보를 사용하여 평가를 진행합니다.
다음 절차를 따릅니다:

1. 각 사용자마다
1. 할인 기준 이상인 이모티콘만 선택
2. 가격 합계를 구함
2. 가격 합계가 사용자의 가격 기준 이상이면
• 구독자 수 += 1
3. 그렇지 않다면
• 판매 수익에 해당 가격만큼 추가

모든 사용자 평가가 끝나면,
현재 할인 조합에 대한 [구독자 수, 판매 수익] 정보를 계산할 수 있습니다.

🔁 최대값 갱신 로직

• 현재 할인 조합의 결과가 기존 저장된 최대값보다
• 구독자 수가 더 많으면 → 무조건 갱신
• 구독자 수가 같고, 판매 수익이 더 많으면 → 갱신

이렇게 해서 가장 이모티콘 플러스 가입자를 많이 확보할 수 있는 할인 조합을 찾을 수 있습니다.

전체코드

• 주석 없이 지금 수정된 전체코드

def DFS(depth, discount):
    global users, emotions, N, max_vals

    if depth == N:
        vals = [0, 0]
        for user in users:
            user_sum = 0
            for i in range(N):
                if discount[i] >= user[0]:
                    user_sum += ((100 - discount[i]) * emotions[i]) // 100
            if user_sum >= user[1]:
                vals[0] += 1
            else:
                vals[1] += user_sum
        if vals[0] > max_vals[0]:
            max_vals = vals
        elif vals[0] == max_vals[0] and vals[1] > max_vals[1]:
            max_vals = vals
        return

    for rate in [10, 20, 30, 40]:
        discount.append(rate)
        DFS(depth + 1, discount)
        discount.pop()

def solution(users_input, emotions_input):
    global users, emotions, N, max_vals
    users = users_input
    emotions = emotions_input
    N = len(emotions)
    max_vals = [0, 0]
    DFS(0, [])
    return max_vals

결론

이 문제는 모든 이모티콘에 대해 가능한 할인율 조합을 만들어가며
각 조합에 대해 사용자들이 어떤 행동을 하는지를 시뮬레이션하는 완전탐색 문제입니다.

• 할인 조합은 DFS로 생성하고
• 사용자 조건을 평가하여 구독 여부와 수익을 계산하며
• 최대 가입자 수와 최대 수익을 조건에 따라 갱신하는 구조입니다.

비록 탐색 공간이 크지만, 이모티콘 개수가 최대 7개이기 때문에
4^7 = 16,384가지 조합만 확인하면 되어, 완전탐색이 가능한 문제입니다.
DFS를 구현하는 방법과 조건 분기, 시뮬레이션 평가 방식의 훈련에 매우 좋은 문제입니다.

---