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

1. 문제 - 프로그래머스 할인행사

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

 

✅ 풀이

모든 이모티콘마다 모든 할인률을 적용하여 케이스를 따지면 된다.

users의 길이는 최대가 100, 할인율은 10/20/30/40으로 4개, emotion의 길이는 7개이므로 완전탐색이 가능하다.

 

def solution(users, emoticons):
    answer = []
    discount_list = [10, 20, 30, 40]    # 할인율은 10, 20, 30, 40으로 설정
    combinations = []     # 각 이모티콘 별 모든 할인률 조합
    
    def dfs(arr, depth):
        if len(arr) == depth:
            combinations.append(arr[:])    # 값을 복사한 새로운 배열 생성 후 추가
            return
        
        for discount in discount_list:
            arr[depth] += discount
            dfs(arr, depth+1)
            arr[depth] -= discount
            
    dfs([0] * len(emoticons), 0)
        
    for combi in combinations:             # 모든 이모티콘 별 할인 조합마다
        join, user_prices = 0, [0] * len(users)     # 이모티콘 플러스 가입, 이모티콘 총 구매 금액을 구하여 answer 배열에 후보지로 추가한다.
        for i, emoji_discount in enumerate(combi):
            for u in range(len(users)):
                if emoji_discount >= users[u][0]:     # 각 이모티콘의 할인율이 각 유저가 생각하는 할인율보다 크거나 같을 경우
                    user_prices[u] += emoticons[i] * (1 - emoji_discount / 100)     # 해당 이모티콘을 구매함
                    
        for i, price in enumerate(user_prices):
            if price >= users[i][1]:      # 유저마다 이모티콘 총 구매 가격이 유저가 생각하는 마지노선 가격보다 크거나 같다면, 이모티콘 플러스를 구매하고 모든 이모티콘에 대한 구매를 취소한다.
                join += 1          # 이모티콘 플러스 구매
                user_prices[i] = 0   # 해당 유저의 모든 이모티콘 구매금액 취소
                
        total = sum(user_prices)       # 모든 이모티콘 구매금액 구하기
        answer.append([join, total])    # 후보지 answer에 추가
        
    return max(answer, key=lambda x:(x[0], x[1]))     # 후보지 중에, 문제 조건대로 이모티콘 플러스 서비스 가입자가 최대인 순으로 정렬하고 이후에 이모티콘 판매량이 가장 큰 경우의 후보지를 선택한다.

 

여기서 DFS 코드에서 할인율 조합 배열 추가할 때

combinations.append(arr)가 아닌 combinations.append(arr[:]) 해야하는 이유는
arr는 call-by-reference이므로 나중에 값이 바뀌면 combinations안의 배열 값도 바뀌므로, 값 자체를 복사해야한다.

 

✅ 다른 사람 풀이

꼭 백트래킹을 활용하지 않아도 중복 순열 라이브러리를 활용하여 모든 조합들을 만들어낼 수 있다.

(중복 순열인 이유는 할인율이 중복 가능하며 순서에 상관 없기때문)

중복순열은 from itertools import product(list, repeat=n) 으로 생성 가능하다.

 

from itertools import product

def solution(users, emoticons):
    answer = []
    discount_list = [10, 20, 30, 40]    # 할인율은 10, 20, 30, 40으로 설정
    combinations = product(discount_list, repeat=len(emoticons))     # 각 이모티콘 별 모든 할인률 조합을 중복순열을 통해 생성한다.
        
    for combi in combinations:             # 모든 이모티콘 별 할인 조합마다
        join, user_prices = 0, [0] * len(users)     # 이모티콘 플러스 가입, 이모티콘 총 구매 금액을 구하여 answer 배열에 후보지로 추가한다.
        for i, emoji_discount in enumerate(combi):
            for u in range(len(users)):
                if emoji_discount >= users[u][0]:     # 각 이모티콘의 할인율이 각 유저가 생각하는 할인율보다 크거나 같을 경우
                    user_prices[u] += emoticons[i] * (1 - emoji_discount / 100)     # 해당 이모티콘을 구매함
                    
        for i, price in enumerate(user_prices):
            if price >= users[i][1]:      # 유저마다 이모티콘 총 구매 가격이 유저가 생각하는 마지노선 가격보다 크거나 같다면, 이모티콘 플러스를 구매하고 모든 이모티콘에 대한 구매를 취소한다.
                join += 1          # 이모티콘 플러스 구매
                user_prices[i] = 0   # 해당 유저의 모든 이모티콘 구매금액 취소
                
        total = sum(user_prices)       # 모든 이모티콘 구매금액 구하기
        answer.append([join, total])    # 후보지 answer에 추가
        
    return max(answer, key=lambda x:(x[0], x[1]))     # 후보지 중에, 문제 조건대로 이모티콘 플러스 서비스 가입자가 최대인 순으로 정렬하고 이후에 이모티콘 판매량이 가장 큰 경우의 후보지를 선택한다.

 

오늘 배운 점

1. Python 배열 복사 관련

배열 a, b 변수가 있을때

- a = b는 call-by-reference로 복사한다 (참조 복사) 즉 값을 복사하는게 아니라 배열의 참조값을 복사하는 것임

- 따라서 값을 복사하여 배열을 복사하려면

* 1차원 배열: b = a[:] / import copy, b = copy.copy(a)

* 2차원 배열 / import copy, b = copy.deepcopy(a)

 

2. 중복순열, 중복조합

- 중복순열: from itertools import product(list, repeat=n)

- 중복조합: from itertools import combinations_with_replacement(list, n)