[Programmers] 이모티콘 할인행사

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

프로그래머스

 

시도

# 1. 가입자 최대한 늘리기
# 2. 판매액 최대한 늘리기
# n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매 (10 20 30 40 할인)
# 각 사용자들 자신 기준에 따라 일정선 이상 할인하면 이모티콘 모두 구매
# 이모티콘 구매 비용 합이 일정 가격 이상 되면, 구매 모두 취소하고 플러스 가입

# 1. 가장 할인율 낮은 사람 기준으로 높은 사람까지 해보면서 (가입자수, 총 판매액) 저장
# 2. 가입자수가 가장 많은 것 중에 판매액 높은거 고르기
import math
def solution(users, emoticons):
    answer = []
    users.sort(key=lambda x:x[0])
    join_total = {}

    for percent, _ in users: # 퍼센트 작은것부터 하나씩 확인
        discount = math.ceil(percent/10)*10 # 할인율
        
        join_num = 0
        total_price = 0
        for percent, price in users: # 해당 할인율에 대해 모두 계산해보기 (한 사람)
            total = 0
            if percent <= discount:
                for emoticon in emoticons: # 모든 이모티콘 탐색 (구매 할지 안할지)
                    total += (emoticon-int(emoticon*(discount/100)))
                
            if total >= price:
                join_num += 1 # 이모티콘 플러스 가입
            total_price += total # 총 매출에 더하기
        
        if join_total.get(join_num) == None:
            join_total[join_num] = [total_price]
        else:
            join_total[join_num].append(total_price)
        
                
                    
    print(join_total)
    
    
    return answer

일단, 문제 이해를 잘못하고 냅다 풀어버렸다.

이모티콘마다 할인율이 다를 수 있는데, 다 동일하게 적용된다고 생각하고 풀었다.

그렇게 문제를 다시 읽었는데, 할인율이 다 다르면 도대체 어떻게 로직을 짜야하지 ?? 

 

생각하다 풀이를 봤다.

https://velog.io/@dh1010a/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4150368-%EC%9D%B4%EB%AA%A8%ED%8B%B0%EC%BD%98-%ED%95%A0%EC%9D%B8%ED%96%89%EC%82%AC

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

접근 방법

각 이모티콘 할인율이 10~40% 사이로 각각 정해진다.

-> 모든 경우의 수를 확인해봐야 한다. 조합

이런 경우 combination 이나 permutations으로 구하거나 dfs(재귀)를 활용할 수 있다.

여기선 할인율 조합이 2차원이기 때문에 재귀를 활용한다.

따라서, 모든 할인율의 경우의 수가 생겼다면, 문제 조건에 맞게 플러스를 가입할지, 이모티콘만 구매할지 결정하고

그 중 가장 많이 가입하고 매출이 높은 경우의 수를 갱신하면 된다.

 

풀이

from itertools import product


def solution(users, emoticons):
    answer = []
    sales = [10, 20, 30, 40]    # 이모티콘의 할인율
    
    for case in product(sales, repeat=len(emoticons)):    # 이모티콘마다 할인율을 적용하는 모든 경우를 체크
        result = [0, 0]
        for user in users:    # 유저마다 이모티콘 구매 후 가격 체크
            temp = 0    # user의 이모티콘 구입 지불 비용
            for idx, sale in enumerate(case):
                if sale >= user[0]:    # 이모티콘 할인율이 유저가 원하는 할인율 이상이면 구매
                    temp += emoticons[idx] * (100 - sale) // 100

            if temp >= user[1]:    # 유저가 생각하는 예산보다 초과하는 경우 이모티콘 플러스에 가입
                result[0] += 1    # result에 이모티콘 플러스 가입자 카운트 +1
            else:
                result[1] += temp    # 이모티콘 플러스에 가입하지 않는다면 result에 이모티콘 구매 가격 누적

        answer.append(result)    # 해당 할인율 경우에서 구한 결과값을 answer에 추가

    answer.sort(key=lambda x: (-x[0], -x[1]))    # 이모티콘 플러스 가입자 최대(우선순위), 이모티콘 판매액 최대로 정렬
    
    return answer[0]

다시 보니 문제를 아예 잘못 이해했었다.

"이모티콘 플러스를 구매하거나, 이모티콘을 구매하거나" 라고 했으니, 이모티콘 플러스에 가입했다면 매출액에 더해주면 안된다..

배운점

from itertools import product

iterator = ['a', 'b', 'v', 'd']
product(iterator, repeat = 2)

위와 같이 product 함수를 통해 중복 순열을 쉽게 구할 수 있다. (순서 0, 중복 0)

 

문제 풀이 핵심은 주어진 조건을 잘 보는 것이다.

- user의 길이는 100 이하.

- 할인율은 10%, 20%, 30%, 40% 4가지.

- 이모티콘의 최대 개수는 7개 이하.

 

문제 조건의 입력값이 생각보다 적다. -> 즉, 완전 탐색으로 풀 수 있다 !

 

조건 꼼꼼히 확인

문제 풀이 방법은 조건에서 찾자. (어떤 알고리즘을 쓸 건지)