카카오 [이모티콘 할인행사] 문제풀이

문제 

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

프로그래머스

 

 

문제 접근 방식

이모티콘의 할인율을 조정해가면서 플러스 가입자 및 판매액을 최대로 하는 할인 조합을 구하는 문제이다. 모든 할인율을 조정해가면서, 각 이모티콘의 할인율에 맞춰 사용자들의 플러스 가입 및 판매액을 구해 비교하면 된다. 

1. 중복순열을 통해 할인율을 조합한다.
    1.1. 해당 할인율을 기준으로 사용자의 판매액을 조사하고, 해당 판매액에 맞춰 플러스 가입 유무를 확인한다.
    1.2. 각 사용자의 플러스 가입 및 판매액을 해당 할인율의 플러스 가입자수 및 판매액에 더해준다.
    1.3. 전체 플러스 가입자 및 판매액 갱신이 필요하다면 갱신해준다.
2. 최대 플러스 가입자 및 판매액을 반환한다.

 

 

시간 복잡도

할인율 [10%, 20%, 30%, 40%] 를 중복순열로 조합해야하며, 이모티콘의 최대 개수가 7개 이기 때문에, 4^7 = 2^14 = 약 4000가지 경우의 수가 발생한다. 최대 이용자 수가 100명이기 때문에 최대 경우의 수는 4x 1e5가지가 되고, 이를 완전탐색하기 때문에 시간내에 동작한다.

 

코드

from itertools import product

def solution(users, emoticons):
    PERCENTAGES=[10,20,30,40]
    e_size=len(emoticons)
    
    # 최종 plus 가입자, 매출 -> 계속 갱신해준다.
    answer_plus,answer_revenue=0,0
    
    # 할인율을 중복순열로 조합하고, 각 조합일때의 plus 가입자 및 매출을 구하고, answer와 비교하여 갱신한다.
    for discounts in list(product(PERCENTAGES,repeat=e_size)):
        total_plus=0
        total_revenue=0
        for i in range(len(users)): 
            # 사용자의 기준 비율 및 가격
            d_standard=users[i][0]
            p_standard=users[i][1]
            revenue=0
            
            # 이모티콘을 순회하며 현재 할인율에 따른 판매액을 구한다.
            for j in range(e_size):
                if discounts[j] >=d_standard:
                    revenue+=emoticons[j]*(100-discounts[j])/100
            
            # 판매가격이 플러스 가격 기준 이상이라면 플러스를 구매, 아닌 경우 총판매액에 추가한다.
            if revenue>=p_standard:
                total_plus+=1
            else:
                total_revenue+=revenue
                
        # 이전 plus , 판매액과 비교하여 최댓값으로 갱신한다.
        if total_plus> answer_plus:
            answer_plus=total_plus
            answer_revenue=total_revenue
        elif total_plus==answer_plus and total_revenue>answer_revenue:
            answer_revenue=total_revenue
       
    # 최종 플러스 가입자 수 및 판매액을 반환한다.
    answer = [answer_plus,answer_revenue]
    return answer

 

 

회고

구현 + 중복순열을 사용한 완전탐색 문제