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

프로그래머스

정답 코드

data = [10, 20, 30, 40]
discount = []

def dfs(temp, depth):
    if depth == len(temp):
        discount.append(temp)
        return

    for d in data:
        temp[depth] += d
        dfs(temp, depth + 1)
        temp[depth] -= d


def solution(users, emoticons):
    max_users = 0
    max_price = 0

    dfs([0] * len(emoticons), 0)

    for d in range(len(discount)):
        join, price = 0, [0] * len(users)
        for e in range(len(emoticons)):
            for u in range(len(users)):
                if users[u][0] <= discount[d][e]:
                    price[u] += emoticons[e] * (100 - discount[d][e]) / 100

        for u in range(len(users)):
            if price[u] >= users[u][1]:
                join += 1
                price[u] = 0

        if join >= max_users:
            if join == max_users:
                max_price = max(max_price, sum(price))
            else:
                max_price = sum(price)
            max_users = join
        
    return max_users, max_price

문제 풀이

1. `dfs` 함수를 호출하여 가능한 모든 할인 조합을 생성하고 `discount` 리스트에 저장합니다.

2. `discount` 리스트에 있는 할인 조합을 하나씩 꺼내면서 유저가 할인 행사에 참여하는 수를 계산합니다.

3. 유저가 할인 행사에 참여하면 해당 유저의 가격을 0으로 초기화합니다. 이렇게 하면 유저가 한 번 할인 행사에 참여한 뒤에도 다른 할인 조합에 참여할 수 있습니다.

4. 각 할인 조합마다 유저가 참여하는 수를 확인하여 최대 매출과 그 때의 참여하는 유저 수를 갱신합니다.

5. 최종적으로 최대 매출과 그 때의 참여하는 유저 수를 반환합니다.

이 코드는 가능한 모든 할인 조합을 탐색하고, 모든 조합에 대해 가격을 계산하므로 시간 복잡도가 큽니다. 따라서 입력 크기가 커지면 실행 시간이 길어질 수 있습니다. 하지만 제한된 입력 크기에서는 정확한 결과를 제공할 수 있습니다.