문제 요약
이모티콘마다 할인율을 정해 판매할 수 있다.
할인율은 다음 네 가지 중 하나다.
10%, 20%, 30%, 40%각 사용자는 다음 기준을 가진다.
- 자신의 기준 할인율 이상인 이모티콘만 구매한다.
- 구매 금액 합이 자신의 기준 가격 이상이면 구매를 취소하고 이모티콘 플러스에 가입한다.
목표는 다음 우선순위를 따른다.
- 이모티콘 플러스 가입자 수를 최대화한다.
- 가입자 수가 같다면 이모티콘 판매액을 최대화한다.
핵심 아이디어
이모티콘마다 선택할 수 있는 할인율은 4가지다.
이모티콘 개수를 m이라고 하면 가능한 할인율 조합 수는 다음과 같다.
4^m프로그래머스 기준으로 이모티콘 개수는 크지 않기 때문에 모든 할인율 조합을 완전 탐색할 수 있다.
각 할인율 조합마다 모든 사용자를 확인해서 다음 값을 계산한다.
- 이모티콘 플러스 가입자 수
- 이모티콘 판매액
그리고 기존 최적값과 비교해 더 좋은 결과를 저장한다.
풀이 과정
1. 할인율 조합 생성
각 이모티콘에 대해 10, 20, 30, 40 중 하나를 선택해야 한다.
Python의 itertools.product를 사용하면 모든 조합을 쉽게 만들 수 있다.
product([10, 20, 30, 40], repeat=len(emoticons))2. 사용자별 구매 금액 계산
사용자 정보는 다음과 같다.
[기준 할인율, 가입 기준 금액]사용자는 자신의 기준 할인율 이상으로 할인하는 이모티콘만 구매한다.
if discount >= user_discount:
total += discounted_price3. 가입 여부 판단
구매 금액이 사용자의 가입 기준 금액 이상이면 이모티콘을 구매하지 않고 서비스에 가입한다.
if total >= user_limit:
subscribers += 1
else:
sales += total4. 최적값 갱신
가입자 수가 더 많으면 무조건 갱신한다.
가입자 수가 같다면 판매액이 더 큰 경우 갱신한다.
if subscribers > best_subscribers:
...
elif subscribers == best_subscribers and sales > best_sales:
...Python 코드
from itertools import product
def solution(users, emoticons):
discount_rates = [10, 20, 30, 40]
best_subscribers = 0
best_sales = 0
for discounts in product(discount_rates, repeat=len(emoticons)):
subscribers = 0
sales = 0
for user_discount, user_limit in users:
total = 0
for discount, price in zip(discounts, emoticons):
if discount >= user_discount:
total += price * (100 - discount) // 100
if total >= user_limit:
subscribers += 1
else:
sales += total
if subscribers > best_subscribers:
best_subscribers = subscribers
best_sales = sales
elif subscribers == best_subscribers and sales > best_sales:
best_sales = sales
return [best_subscribers, best_sales]코드 설명
할인율 목록
discount_rates = [10, 20, 30, 40]각 이모티콘에 적용할 수 있는 할인율이다.
모든 할인율 조합 탐색
for discounts in product(discount_rates, repeat=len(emoticons)):discounts는 각 이모티콘에 적용된 할인율 조합이다.
예를 들어 이모티콘이 2개라면 다음과 같은 조합들이 만들어진다.
(10, 10)
(10, 20)
(10, 30)
...
(40, 40)사용자의 구매 금액 계산
if discount >= user_discount:
total += price * (100 - discount) // 100사용자의 기준 할인율 이상인 이모티콘만 구매한다.
할인된 가격은 정수 나눗셈으로 계산한다.
가입자 수와 판매액 계산
if total >= user_limit:
subscribers += 1
else:
sales += total구매 금액이 기준 금액 이상이면 사용자는 이모티콘 플러스에 가입한다.
이 경우 이모티콘 구매는 취소되므로 판매액에는 더하지 않는다.
정답 갱신
if subscribers > best_subscribers:
best_subscribers = subscribers
best_sales = sales
elif subscribers == best_subscribers and sales > best_sales:
best_sales = sales문제의 목표는 가입자 수가 1순위이고, 판매액이 2순위다.
따라서 가입자 수를 먼저 비교하고, 가입자 수가 같을 때만 판매액을 비교한다.
시간 복잡도
사용자 수를 n, 이모티콘 수를 m이라고 하자.
할인율 조합은 4^m개다.
각 조합마다 모든 사용자와 모든 이모티콘을 확인한다.
O(4^m * n * m)이모티콘 개수가 작기 때문에 완전 탐색으로 충분히 해결할 수 있다.
공간 복잡도
할인율 조합과 몇 개의 변수만 사용한다.
O(m)product가 현재 조합을 튜플로 만들어 사용하므로 조합 길이만큼의 공간이 필요하다.
정리
이 문제는 할인율 조합을 전부 확인하는 완전 탐색 문제다.
핵심은 다음과 같다.
- 이모티콘마다 4가지 할인율 중 하나를 선택한다.
- 각 할인율 조합마다 사용자별 구매 금액을 계산한다.
- 가입자 수를 먼저 최대화하고, 그다음 판매액을 최대화한다.
목표 우선순위만 정확히 반영하면 간단하게 해결할 수 있다.
