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

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

 

프로그래머스

 

난이도 : Level 2 
알고리즘 유형 : 완전탐색, 조합 
풀이 시간 : 41분 

문제 풀이 

이모티콘 할인행사의 목표 우선순위는 다음과 같다.

1. 서비스 가입자 최대
2. 판매액 최대

카카오톡 사용자들은 자신의 기준이 되는 일정 할인율 이상 할인하는 이모티콘들을 모두 구매한다. 만약, 이모티콘을 구매하는 비용이 사용자의 최대 예산을 넘어간다면 사용자는 이모티콘 서비스를 가입한다.

 

문제를 보면 매우 복잡하고, 완전탐색 진행 시 시간초과가 발생할 것 같지만 막상 계산해보면 전혀 그렇지 않다.

먼저, 모든 이모티콘은 할인율이 다르다고 했으니, 이모티콘 별 할인율을 적용한 새로운 배열을 생성해준다. 이 과정은 재귀함수를 사용하여 진행해주었다. 중복이 가능해야 하기 때문에, 총 시간복잡도로는 $O(7C4) = 약 17000$ 정도가 소요된다. 

이렇게 생성한 새로운 할인율 이모티콘 배열을 사용자 한 명씩 탐색하여 사용자들의 구매 기준을 확인한다. 

 

따라서, 최악의 경우 총 시간복잡도를 계산해보면  $O(7C4 * 100 * 7)$로 약 1200만 시간복잡도가 소요된다.

 

코드

'''
이모티콘 플러스 서비스 가입자 수를 늘리려고 함
목표 우선순위 : 
1. 서비스 가입자 최대
2. 판매액 최대

n명에게 이모티콘 m개를 할인하여 판매
이모니콘 별 할인율은 다름

이모티콘 사거나 서비스 가입 기준
- 자신의 기준에 따라 일정 비율 이상 할인하는 이모니콘 모두 구매
- 구매 비용의 합이 일정 가격 이상이 된다면 구매 모두 취소 후 서비스에 가입

풀이법 : 완전탐색, 백트래킹
이모티콘마다 할인율은 다를 수 있음 & 할인율은 총 4개 중 하나로 설정
=> 할인율과 이모티콘 가격 배열 만들어놓기
'''

def solution(users, emoticons):
    
    def dfs(depth, e, m):
        if depth == m:
            discount_emoticons.append(e)
            return
        else:
            for rate in [10, 20, 30, 40]:
                tmp_cost = emoticons[depth] * (100 - rate) // 100
                dfs(depth + 1, e + [(rate, tmp_cost)], m)

                
    answer = [0, 0]
    n = len(users)
    m = len(emoticons)
    # 할인율 -> 사람 -> 이모티콘
    
    discount_emoticons = []
    dfs(0, [], m)
    
    # 이제 돌면서 선택해보기
    for idx in range(len(discount_emoticons)):
        tmp_service = 0
        tmp_amount = 0
        for user in range(n):
            discount_rate, budget = users[user]
            tmp = 0
            for rate, emoticon in discount_emoticons[idx]:
                if discount_rate > rate:
                    continue
                tmp += emoticon
                if tmp >= budget:
                    tmp_service += 1
                    break
            else:
                tmp_amount += tmp
        if tmp_service > answer[0]:
            answer = [tmp_service, tmp_amount]
        elif tmp_service == answer[0]:
            answer = [tmp_service, max(tmp_amount, answer[1])]
        
    return answer

배운 점 

항상 느끼는 거지만 카카오 연습문제는 지문이 매우 길다 .. (삼성만큼은 아니지만) 

처음에 문제를 제대로 읽지 않아 0 ~ 40%의 할인율을 모두 계산하여 저장하였다.. 여기서 시간을 매우 많이 잡아먹었다.

문제 지문이 길어도 당황하지 않고 항상 자세히 읽자 (시간 오래걸린다고 그냥 넘기지 말기)