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

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

프로그래머스

코드를 작성하기 위한 순서는 다음과 같다.

1. 10, 20, 30, 40으로 만들 수 있는 모든 경우의 수를 구해주기 위해서 product 라이브러리를 사용해준다.

2. 문제의 조건에 따라 할인율이 크다면 할인된 금액을 더해준다.

3. 정해진 금액보다 구매 금액이 크다면 이모티콘 구독권 구매수를 증가시킨다.

4. 구독권 수를 기준으로 먼저 내림차순 정렬을 하고 판매 금액을 기준으로 내림차순 정렬을 하면 배열의 첫번째 원소가 답이 된다.

 

from itertools import product #1번

def solution(users, emoticons):
    answer = []
    rate = [10, 20, 30, 40]
    datas = list(product(rate, repeat = len(emoticons))) #1번
    
    for k in range(len(datas)):
        new = [0, 0]
        for i in users:
            now = 0
            for j in range(len(emoticons)):
                if i[0] <= datas[k][j]: #2번
                    now += (100-datas[k][j])/100*emoticons[j]
            if now < i[1]: #3번
                new[1] += now
            else:
                new[0] += 1
                
        answer.append(new)
    answer.sort(key = lambda x:(-x[0], -x[1])) #4번
            
    return answer[0]

 

처음 문제를 접근할 때는 DFS를 사용하여 최댓값을 도출하는 방식으로 접근하려 했으나, 도무지 규칙을 찾을 수가 없었다.

따라서 먼저 시간복잡도를 계산하였더니, 최대 조건에서 약 1000만 정도의 값이 나오는 것을 확인하여 1억보다 작다는 것을 알게 되었다.

또한 할인율이 문제에서 10, 20, 30, 40으로 모두 동일한 것을 바탕으로 만들 수 있는 모든 경우의 수를 사용하여 문제를 풀기로 했다.

파이썬의 product 라이브러리는 permutations과 동일하게 순서를 신경쓰지만 중복을 포함하게 조합을 만드는 라이브러리이다.

product를 사용하여 편리하게 emoticons의 길이가 4인 경우, [10, 10, 10, 10]부터 [40, 40, 40, 40]까지 모든 경우의 수를 만들어서 문제를 해결할 수 있었다.