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

2023 KAKAO BLIND RECRUITMENT - 150368. 이모티콘 할인행사

[Lv. 2]

 

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

프로그래머스

 

풀이

우선, 문제를 다 읽자마자 확인한 것은-

"Brute-Force로 해결할 만 한가?" 였다.

이모티콘의 각 할인율은 10%, 20%, 30%, 40% 중 하나이고,

1 ≤ emoticons의 길이 = m ≤ 7

에서 볼 수 있듯, 이모티콘이 최대 7개이므로, 7^4 = 2041가지 경우의 수 정도만 파악하면 된다.

각 경우의 수마다, user가 어떤 행동을 취하는지를 확인하는 것은 당연히 O(1)의 time complexity로 계산 가능하고,

뭐 user의 최대 수도 아래와 같이 100명이므로... Brute-Force로 구현해도 TLE가 뜨진 않겠다- 싶었던 문제.

1 ≤ users의 길이 = n ≤ 100

대충 계산때려봐도 20만개정도가 max니까 뭐..

 

그럼 이제 구현을 잘 해봐야겠죠..?

 

import sys
sys.setrecursionlimit(10000)

def solution(users, emoticons):
    # 할인율의 중복조합
    d = [10, 20, 30, 40]
    discounts = []

    def p(arr, depth, l):
        if depth == l:
            discounts.append(arr)
            return

        for i in range(4):
            p(arr+[d[i]], depth+1, l)

    # 할인율 리스트 생성
    p([], 0, len(emoticons))

    # 최종 결과.
    answer = [0, 0]

    # 모든 할인율 리스트에 대해 모든 유저의 상황을 확인, 최적의 상황 탐색
    for discount in discounts:
        # 각 할인율 리스트에 대한 총 이모티콘 플러스 가입 유저와 이모티콘 구매 비용
        emo_plus = 0
        emo_total = 0

        for user in users:
            total = 0
            # 각 유저에 대해 각 아이템의 할인율을 대조하여, 살 지 말 지 확인.
            for i in range(len(discount)):
                # 이모티콘의 할인율이 유저가 생각하던 비율보다 높다면 구매
                if user[0] <= discount[i]:
                    total += int(emoticons[i]*((100-discount[i]))/100)

            # 유저가 설정한 가격 이상일 시, 이모티콘 플러스 가입. 아니라면, 이모티콘 총 구매 비용에 합산.
            if total >= user[1]:
                emo_plus += 1
            else:
                emo_total += total

        # 이모티콘 가입자가 더 많다면 무조건 값 대체
        if answer[0] < emo_plus:
            answer = [emo_plus, emo_total]
        # 이모티콘 가입자가 이전과 같다면, 총 판매 비용이 높을 때만 값 대체
        elif answer[0] == emo_plus:
            if answer[1] <= emo_total:
                answer = [emo_plus, emo_total]
                
    return answer