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

문제에 대한 생각 흐름 정리는 다음과 같다.

 

1. 완전 탐색 시간은 최대 얼마나 걸리는가?

적용할 수 있는 할인율은 10%, 20%, 30%, 40% 4가지이고, 

이모티콘은 최대 7개까지 주어지므로 4^7개의 계산 결과 중 최소값을 찾으면 되겠다. 

 

그럼 모든 경우의 수에 대한 배열을 생성하기 위한 함수는 어떤 것을 활용하면 좋을까?

itertools.product(*2d list)를 활용. 

https://www.geeksforgeeks.org/python-all-possible-permutations-of-n-lists/

Python | All possible permutations of N lists - GeeksforGeeks

2. 구독자 수, 판매액 순으로 정렬 후 맨 앞의 것 선택. 

 

import itertools

def solution(users, emoticons):
    
    # 4 * emoticons(m) 배열 만들기.
    promo_cases = list()
    for emo in emoticons:
        cost = []
        for promo in [0.1, 0.2, 0.3, 0.4]:
            cost.append(emo*(1-promo))
        promo_cases.append(cost)
    # print(promo_cases)
    
    # 모든 조합 생성 완료
    all_promos = list(itertools.product(*promo_cases))
    # print(all_promos)
    
    #완전 탐색
    #모든 조합을 하나씩 살펴보며, user->cost순으로 크면 업데이트 
    max_user = 0
    max_cost = 0
    for case in all_promos:
        #(6300.0, 8100.0)
        # 사람마다 가능한 구독 여부와 최종 구매액을 구함. 
        each_uc = list()
        for ratio, buget in users:
            #[40, 1000]
            user = 0 
            cost = 0 
            for af_case, bf_case in zip(case, emoticons):
                #유저 원하는 가격보다 싼 경우, 구매로 이어짐. 
                if bf_case*(1-ratio*0.01) >= af_case:
                    cost+=af_case
                #일정 가격 이상이면 구독자가 되고, 가격이 0이 됨. 
                if cost >= buget:
                    cost = 0
                    user += 1
                    break
                
            each_uc.append((user, cost))
        # print(each_uc)
        #모든 사람에 대한 총 구독 여부와 최종 구매액 구한 후 최적값 갱신. 
        total_user = sum([i[0] for i in each_uc])
        total_cost = sum([i[1] for i in each_uc])
        # print(total_user, total_cost)
        if max_user < total_user:
            max_user = total_user
            max_cost = total_cost
        elif max_cost < total_cost and max_user == total_user:
            max_user = total_user
            max_cost = total_cost
        # print(max_user, max_cost)

    return [max_user, max_cost]