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

문제

https://school.programmers.co.kr/learn/courses/30/lessons/150368

풀이

할인율의 가능한 모든 조합을 product로 구한다.
조합을 순회하면서 user를 순회한다.
이모티콘을 순회하면서 구매 비용 및 이모티콘 플러스 가입자 수를 구한다.

해당 할인 조합에서 나오는 결과값과 이전 결과 값을 비교해서
큰 결과 값을 answer에 초기화한다.

from itertools import product

def solution(users, emoticons):
    plus_user = 0
    sales_amount = 0
    sales_type = list(product([10,20,30,40], repeat=len(emoticons)))

    answer = [0,0]
    for type in sales_type:
        sign_up = 0
        amount = 0
        for target_type, target_price in users:
            price = 0
            for i, emoticon in enumerate(emoticons):
                if target_type <= type[i]:
                    price += int(emoticon // 100 * (100 - type[i]))

            if target_price <= price:
                sign_up += 1
            else:
                amount += price
        
            answer = max(answer, [sign_up, amount])    
            
    return answer

회고

itertools 모듈의 product 함수는 여러 개의 반복 가능한(iterable) 객체를 받아서, 각 객체에서 하나의 요소를 뽑아서 가능한 모든 조합을 생성하는 데 사용됩니다. 즉, 카르테시안 곱(Cartesian product)을 구하는 함수입니다.

예를 들어, product('ABCD', repeat=2)는 두 개의 문자열에서 가능한 모든 조합을 생성합니다. 즉, AA, AB, AC, AD, BA, BB, BC, BD, CA, CB, CC, CD, DA, DB, DC, DD를 생성합니다.

product 함수의 시간 복잡도는 입력값에 따라 다르며, 각 반복 가능한 객체의 길이를 n, 반복 가능한 객체의 개수를 m이라고 하면 시간 복잡도는 O(n^m)입니다. 따라서, 입력값이 매우 큰 경우, 시간이 매우 오래 걸릴 수 있습니다.

max의 파라미터가 배열일 경우 첫 번째 요소를 기준으로 정렬한다.
만약 첫번째 요소가 같을 경우 두 번째 요소를 기준으로 정렬한다.