프로그래머스 - 이모티콘 할인행사(2023 KAKAO BLIND RECRUITMENT) / Level 2 / Python

문제 📋

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

풀이 📝

from itertools import product

def solution(users, emoticons):
    answer = []
    m = len(emoticons)
    discount = [10, 20, 30, 40]
    
    cases = list(product(discount, repeat=m))
    
    for case in cases:
        sub = 0
        amount = 0
        
        prices = []
        for i in range(m):
            prices.append((emoticons[i] // 100) * (100 - case[i]))
    
        for target, threshold in users:
            money = 0
            
            for i in range(m):
                if case[i] >= target:
                    money += prices[i]
            if money >= threshold:
                sub += 1
            else:
                amount += money
        answer.append((sub, amount))
    
    answer.sort(key=lambda x: (-x[0], -x[1]))
    
    return answer[0]

1. 문제 정의
   이모티콘의 할인율을 탐색했을 때
   서비스 가입자, 매출액의 최댓값을 찾는 문제이다.
   (서비스 가입자가 같으면 매출액이 최대가 되도록)

2. 시간 복잡도 계산
   완전 탐색이 먼저 가능한지 계산해 봤다.
   먼저 가능한 이모티콘의 가격들은 중복조합으로 구할 수 있고
   4^7이기 때문에 약 16,000이다.

   또한 user의 수가 최대 100이기 때문에 총 탐색 범위는 약 1,600,000이다.
   따라서 충분히 완전 탐색이 가능하다고 판단했다.

3. 문제 풀이
   itertools.product 라이브러리로 중복조합을 생성해 주었으며
   문제에 조건에 따라 계산해 주고 마지막엔 (가입자 수, 매출액) 기준으로 정렬해 주었다.

4. 예외 사항
   기타 특이사항 없음.