Programmers_LV2_이모티콘 할인행사(2023 KAKAO BLIND RECRUITMENT)

할인율의 경우의 수는 4개이다. 유저는 1~100명 즉 100가지 경우의수이다. 가능한 이모티콘의 수는 7가지이다.

최대 연산의 수를 생각해볼 때 각 이모티콘마다 할인율은 중복으로 설정이 가능하므로 4의 7승이다. 계산기로 두들겨 보면 정확히 16,384가지의 경우의 수를 가진다. 즉 16,384 x 7 x 100 => 약 1150만개의 연산이 나온다. 1억개 정도의 연산이 나오지 않는다면 경우의 수를 모두 고려해서 코딩해도 될 것이다. 문제가 복잡할 경우에 오히려 자료구조보다는 순수하게 이 복잡성을 구현하는 것에 초점을 두는 듯 하다. 복잡하므로 경우의 수 range를 줄이는 것이다. (출제자의 의도)

할인율 중복순열 리스트를 product함수를 통해 만든다. 그리고 모든 경우의 수를 리스트안에 넣고 sort해서 return한다. 흐름 그대로 따라서 코딩하면 어렵지 않게 코딩가능하다. 중복순열을 직접 만들려고 하다가 시간이 걸렸던 것을 product로 대체했을 때 코딩시간은 한 시간정도였다.

from itertools import product

def solution(users, emoticons):
    rate = [10, 20, 30, 40] # 가능한 할인율
    
    repeat_n = len(emoticons)
    
    rate_lst = list(product(rate, repeat = repeat_n)) # 할인율 조합 리스트 만들기
    
    case_lst = [] # rate별 케이스 모을 곳
    for rate in rate_lst:
        emo_plus = 0
        emo_purchase = 0
            
        for user in users:
            
            customer_rate = user[0]
            customer_price = user[1]
            
            # 할인율에 따른 emoticon 가격 리스트
            price_lst = [int(emoticons[i] * (100 - rate[i]) / 100) 
                         for i in range(len(rate))]
            purchase = []
            
            
            for rate_ in rate: # 고객이 살 것에 대한 리스트 0과 1로 나타내기
                if rate_ >= customer_rate: # 고객이 구매할 경우
                    purchase.append(1)
                else: # 고객이 구매 안할 경우
                    purchase.append(0)
            
            # 실제로 고객이 구매할 물건별 결제 가격
            total_purchase = [purchase[i] * price_lst[i] 
                              for i in range(len(price_lst))]
            
            cond = sum(total_purchase) # rate경우의 수에 따른 고객의 전체 구매 가격 
    
            if cond >= customer_price: # 가격을 기준으로 카운트
                emo_plus += 1
            else:
                emo_purchase += cond
        
        case_lst.append([emo_plus, emo_purchase])
        
    case_lst.sort(key= lambda x : (x[0], x[1]), reverse=True)
    return case_lst[0]
# 최대 테스트 시간 6초미만.