[Lv.2 / 프로그래머스 / 파이썬] 이모티콘 할인행사 (2023 KAKAO BLIND RECRUITMENT)

 

 

 

 

프로그래머스

 

 

 

풀이

 

각 이모티콘의 할인율을 적절하게 정하여 최대의 이모티콘 플러스 가입자를 유치하고, 그 때 최대의 이익을 출력해야 한다.

 

알고리즘이 필요하다기 보다는 단순무식한 구현 문제였다. 완전탐색으로 문제를 해결하려고 할 때, 제한 사항이 시간복잡도를 만족하는지 확인해보자.

 

이모티콘의 총 길이는 7이고 할인율은 10, 20, 30, 40 총 4개이다. 그리고 최대 유저는 100명이다. 이 때 생각할 수 있는 완전탐색 알고리즘은 다음과 같다.

 

1. 존재할 수 있는 모든 할인율의 조합을 이모티콘의 길이만큼 구한다.
2. 할인율의 조합을 순회한다.
   1. 유저를 순회한다.
      1. 이모티콘을 순회하며 판매액의 합계를 구한다.
      2. 판매액을 바탕으로 이모티콘 플러스 서비스의 가입 여부와 판매액을 더한다.
   2. 현재 할인율의 조합에 대해 이모티콘 서비스의 가입 여부와 판매액을 구했으므로 다음의 규칙을 수행한다.
      1. 이모티콘 플러스 가입자 수가 이전보다 늘었다면, 서비스 가입자 수와 판매액을 갱신한다.
      2. 가입자 수가 이전과 같다면, 이전 판매액과 현재 판매액 중 최대치를 구해 갱신한다.
3. 결과 반환

 

이 때 제한 사항을 토대로 최대 시간복잡도를 계산해보면 4 ^ 7 * 100 * 7 = 11,468,800 즉, 약 천 만 정도가 되므로 무난하게 통과가 가능한 수준이다. 따라서 위 알고리즘을 토대로 문제를 풀이하면 된다.

 

from itertools import product

def solution(users, emoticons):
    # 모든 할인율의 조합
    all_discount_rates = list(product([10, 20, 30, 40], repeat = len(emoticons)))
    
    ans_e_plus = 0
    ans_profit = 0
    for discount_rates in all_discount_rates:
        e_plus = 0
        profit = 0
        # 유저를 순회하며 각 유저의 이모티콘 플러스 서비스 가입 여부 및 구매 금액 계산
        for require_rate, maximum_price in users:
            total_price = 0
            for i in range(len(emoticons)):
                # 할인율이 고객이 원하는 할인율을 넘는지
                if discount_rates[i] >= require_rate:
                    total_price += ((100 - discount_rates[i]) * emoticons[i]) / 100
                    # 구매 비용 초과이므로 이모티콘 플러스 서비스 가입
                    if total_price >= maximum_price:
                        e_plus += 1
                        break
            else:
                profit += total_price
                continue
        
        # 결과 갱신
        if e_plus > ans_e_plus:
            ans_e_plus = e_plus
            ans_profit = profit
        elif e_plus == ans_e_plus:
            ans_profit = max(profit, ans_profit)
    
    return [ans_e_plus, ans_profit]