[Python][카카오기출] 이모티콘 할인행사

 

 

목차

 

 

🫡 Overview

체감 난이도: ★★☆☆☆

소요시간: 

문제 레벨: Lv2 / 문제 유형: 구현
풀이 상태:  스스로 해결
추후: 간단복습

 

---

문제 링크

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

목적 

이모티콘을 할인하여 판매할 건데, 

다음과 같은 목표를 달성해야함. 

1 순위) 이모티콘 서비스 사용자의 수를 늘리기

2 순위) 이모티콘 매출을 늘리기 

 

 

 

 

요구사항 분석

- 변수는 각 이모티콘 별 할인율로 설정

처음엔 각 이모티콘 별로 목표를 달성하는 할인율을 이분 탐색으로 풀려고 해서 헤맸다.

문제를 다시 읽어보니, 이모티콘 할인율이 4개 (10%, 20%, 30%, 40% ) 밖에 없어서 완전 탐색으로 풀었다. 

선택한 알고리즘: 완전 탐색 

 

풀이 방법:

모든 이모티콘 할인율 경우의 수에 대해서 각 유저들이 어떤 이모티콘을 구매할 것인지 계산해야한다. 

 

시간 복잡도 계산 : 

(1) 이모티콘 할인율의 경우의 수 : 최대 4^(이모티콘 개수)  = O(4^7)

    - 예를 들어 n=2 인 경우 [10%,10%], [10%,20%],[10%, 30%], [10%,40%], [20%,10%], .... , [40%, 40%] 총 16가지 경우의 수가 나온다. 

   - 따라서 재귀로 중복 순열을 구현하였다. 

 

 (2) 각 유저들에 대해서 어떤 이모티콘을 구매할 것인가? 유저 (최대 100명) x 이모티콘 개수(최대 7) = O(700)

 

=> O(4^7*700) : SAFE

 

최대 이모티콘 개수와 최대 유저의 수가 적기 때문에, 가능했던 풀이라고 생각한다. 

 

 

 

풀이 과정

크게 2가지 파트로 구현했다. 

 

(1) 재귀로 각 이모티콘의 할인율 중복 순열 구하기 

(2) 주어진 조건 대로 단순 구현

 

 

 

 

 

내 코드

permutation_lst = [] # 모든 중복 수열
permutation = [] # 중복 수열 
discounts = [0.1,0.2,0.3,0.4] # lst

def DFS(L, max_length):
    if L >= max_length:
        permutation_lst.append(permutation[:]) # 정답 저장 
        return 
    for i in range(len(discounts)):
        permutation.append(discounts[i])
        DFS(L+1, max_length)
        permutation.pop()

def solution(users, emoticons):
    answer = [] # [[가입 인원,] 
    DFS(0,len(emoticons))
    global permutation_lst
    
    for permutation in permutation_lst: # 각 % 케이스 이모지 번호, 퍼센티지 
        total_price = 0 # 모든 사용자의 총 구매 금액
        num_member = 0 # 서비스 가입자 수 
        purchased = [] # 구매한 이모티콘 인덱스 저장 
        for k, user in enumerate(users): # 각 유저에 대해서 구매 가능한 이모지와 총 금액 확인하기 
            user_rate_thres, user_price_thres = user
            user_rate_thres = user_rate_thres*0.01
            user_purchase = 0 # 해당 유저가 구매한 이모티콘 총 총 가격
            for i, emoticon_price in enumerate(emoticons):
                discount_rate = permutation[i]
                if discount_rate >= user_rate_thres: # 구매할 경우: 사용자 비율 이상 할인
                    discounted_price = emoticon_price*(1-discount_rate)
                    user_purchase += discounted_price
                    purchased.append(i)
            if user_purchase >= user_price_thres:
                num_member +=1 
                user_purchase = 0
            total_price += user_purchase
        answer.append([num_member, total_price])
    # 정답 리턴
    answer.sort(key = lambda x:(-x[0], -x[1]))
    return answer[0]

 

 

풀이와 비교

내가 이해한 바와 같이 모든 경우의 수를 탐색하는 문제 였다. 

---

 

소감

아자아자!

---

레퍼런스 

• 2023 카카오 신입 공채 1차 온라인 테스트 

 

https://tech.kakao.com/posts/567

2023 카카오 신입 공채 1차 온라인 코딩 테스트 for Tech developers 문제해설 - tech.kakao.com

 

 

 

#백준 #코딩테스트 #알고리즘 #python #파이썬