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

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

🔗 문제 링크

---

문제 설명 📄

이모티콘 할인 행사를 진행할 때, 사용자들이 이모티콘을 구매하거나 이모티콘 플러스 서비스에 가입하는 최적의 경우를 찾아야 합니다. 할인율을 다르게 적용했을 때의 결과를 계산하여, 가입자 수가 최대가 되는 경우를 찾고, 같은 가입자 수라면 매출이 최대가 되는 경우를 선택해야 합니다.

---

문제 접근 방식 💡

• 할인율(10%, 20%, 30%, 40%)을 이모티콘마다 다르게 적용할 수 있다.
• 각 사용자는 특정 할인율 이상일 때만 구매하며, 구매 금액이 특정 금액 이상이면 이모티콘 플러스에 가입한다.
• 완전 탐색(BFS)을 사용하여 모든 할인 조합을 탐색하고 최적의 결과를 찾는다.
• bfs() 함수는 현재까지의 구매 금액을 추적하며, 모든 이모티콘에 대해 할인율을 적용한 경우를 탐색한다.
• 최종적으로 가장 많은 가입자를 확보하고, 같은 가입자 수라면 매출이 최대가 되도록 설정한다.

---

Solution 💻

def solution(users, emoticons):
    global answer
    answer = [0, 0]

    def bfs(totals, eindex):
        global answer
        if len(emoticons) == eindex:
            plus = 0
            total = 0
            for t in range(len(totals)):
                if totals[t] >= users[t][1]:
                    plus += 1
                else:
                    total += totals[t]

            if answer[0] < plus:
                answer[0] = plus
                answer[1] = total
            elif answer[0] == plus:
                answer[1] = max(total, answer[1])
            return
        else:
            for discount in [10, 20, 30, 40]:
                newTotals = totals[:]
                for i in range(len(users)):
                    if users[i][0] <= discount:
                        newTotals[i] += (emoticons[eindex] * (1 - discount * 0.01))
                bfs(newTotals, eindex + 1)

    bfs([0] * len(users), 0)
    return answer

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(4^E x U)
  • E: 이모티콘 개수
  • U : 사용자 수
  • 각 이모티콘에 대해 4가지 할인율을 적용하는 경우의 수가 4^E이므로, 이모티콘 개수가 많아지면 계산량이 증가함.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(U + E)
  • U(사용자 수) 크기의 리스트(totals)와 E(이모티콘 개수) 깊이의 재귀 호출 스택 사용.

---

리팩토링 🛠️

from itertools import product

def solution(users, emoticons):
    max_plus, max_sales = 0, 0
    discounts = [10, 20, 30, 40]
    
    for discount_comb in product(discounts, repeat=len(emoticons)):
        plus, sales = 0, 0
        user_spending = [0] * len(users)

        for i, discount in enumerate(discount_comb):
            price = emoticons[i] * (1 - discount * 0.01)
            for j, (min_discount, min_price) in enumerate(users):
                if min_discount <= discount:
                    user_spending[j] += price

        for j, (_, min_price) in enumerate(users):
            if user_spending[j] >= min_price:
                plus += 1
            else:
                sales += user_spending[j]

        if plus > max_plus or (plus == max_plus and sales > max_sales):
            max_plus, max_sales = plus, sales

    return [max_plus, max_sales]

시간 복잡도 분석 ⏲️

• 시간 복잡도: O(4^E x U) (같음)
  • 단, itertools.product()를 활용해 코드 가독성을 높이고, 중복 연산을 최소화.

공간 복잡도 분석 🗄️

• 공간 복잡도: O(U)
  • 사용자별 구매 금액을 저장하는 리스트 사용.