코딩테스트 스터디 - 프로그래머스 이모티콘 할인행사 (python)

문제

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

프로그래머스

요약

이모티콘 할인 행사로 이모티콘 플러스 가입자수를 최대화 하면서, 가입자수가 같다면 이모티콘 판매액을 최대화해야합니다.

각 이모티콘은 10,20,30,40 중 하나의 할인률과 가격을 가지며,

각 사용자는 x%이상 세일하는 이모티콘은 무조건 사고, 총 구매액이 y원이 넘어가면 이모티콘 플러스에 가입합니다.

의식의 흐름

단순하게 생각했을 때, 하나씩 다 해보면 됩니다.

이모티콘의 수가 최대 7개기 때문에, 많아봐야 유저수*(4^7) 만큼의 iteration만 하면 됩니다.

어차피 모두 탐색해야하기 때문에 메모리 복사가 적은 DFS로 탐색하기로 했습니다.

구현

자료구조

각 이모티콘이 얼마나 세일을 하는지를 promos 리스트에 저장합니다.

알고리즘

dfs(i, promos) : promos의 i번째 이모티콘의 할인률에 대한 모든 경우의수를 탐색한다.

그렇게 promos의 모든 항목이 값이 정해지면 그때 users와 emoticons 정보를 이용해 이모티콘 플러스 가입자수와 매출액을 구합니다.

이렇게 구한 값 중 최대값을 저장해두고 마지막에 반환합니다.

코드

문제 이해가 처음에 살짝 헷갈렸지만, 이모티콘 수가 7개밖에 안돼서 그냥 다 해보면 되는 문제였습니다.

이것보다 더 빠른 방법이 있을까요?

정답이 찍혀버려서 깊게 생각하고싶지 않아졌지만 다른 방법이 마땅히 떠오르진 않네요.

 

'''
    문제 출처 : https://school.programmers.co.kr/learn/courses/30/lessons/150368
'''
def get_result(users, promos, emoticons):
    total = [0,0]
    for user in users:
        result = [0, 0]
        for i in range(len(emoticons)):
            promo = promos[i]
            price = emoticons[i]
            if promo >= user[0]:
                result[1] += price * (100-promo) / 100
        if result[1] >= user[1]:
            result = [1, 0]
        total[0] += result[0]
        total[1] += result[1]
    return total

answer = [0,0]
def dfs(i, users, promos, emoticons):
    global answer
    if i == len(emoticons):
        newanswer = get_result(users, promos, emoticons)
        if newanswer[0] > answer[0]:
            answer = newanswer
        elif newanswer[0] == answer[0] and newanswer[1] > answer[1]:
            answer = newanswer
        return
    for x in [10,20,30,40]:
        promos[i] = x
        dfs(i+1, users, promos, emoticons)

def solution(users, emoticons):
    global answer
    promos = [10 for i in range(len(emoticons))]
    
    dfs(0, users, promos, emoticons)
    
    return answer