[코딩테스트] KAKAO BILND RECRUIT 기출문제 이모티콘 할인행사

문제 개요

1. 이모티콘 플러스 서비스 가입자 최대
2. 이모티콘 판매액 최대
   1번 우선 그다음 2번
   => 이모티콘 플러스 가입자 수가 최대일 때 판매액을 최대로 하는 경우의 수

• 이모티콘은 10,20,30,40 중 랜덤하게 할인 됨
• 일정 비율이상 할인 시 => 이모티콘 구입
• 이모티콘 구매 비용 합이 일정 가격을 넘는 경우 => 이모티콘 플러스 가입함

단, 각 고객은 비율과 일정 가격이 다르다.

즉, 랜덤으로 할인하는 여러 경우의 수 중 최대의 판매액과 가입자 수를 구하라

접근방식

1. 그리디 알고리즘(?)
   어자피 모두 다 해봐야 한다는 생각이 듬
2. 이 알고리즘은: ✅ 완전 탐색 (Brute Force) 을 사용하여 모든 경우의 수를 시뮬레이션
   ✅ 할인율 조합을 생성하여 모든 경우를 탐색 (itertools.product)
   ✅ 플러스 멤버를 최대로 확보하는 전략을 선택 (탐욕적 선택, Greedy-like)
   =>결론적으로, 완전 탐색 기반의 최적해 탐색 문제라고 볼 수 있습니다. 🚀
3. 각 이모티콘의 할인율이 10,20,30,40 인 케이스 즉 4^n 개를 비교해야함
4. 각 케이스 별로 user 별로 계산해서 이모티콘 플러스 가입자 수와 수익 산정
   • 특정 비율 이상인 이모티콘 탐색
   • 할인된 가격을 합산
   • 특정 가격 이상 이면 플러스 가입

이슈

• 어떻게 4^n개의 케이스를 만들 수 있지?
• 할인율이므로 1-할인율을 곱해야 한다 주의!!

itertools.product 함수 설명

itertools.product는 Python의 데카르트 곱(Cartesian Product) 을 생성하는 함수입니다.
즉, 여러 개의 리스트나 문자열 등의 모든 가능한 조합을 생성할 때 사용됩니다.

기본 문법

python

import itertools itertools.product(iterable1, iterable2, ..., repeat=N)

• iterable1, iterable2, ... : 조합을 만들 여러 개의 리스트 또는 문자열
• repeat=N : 같은 iterable을 N번 반복하여 조합을 생성

이터레이터는 한 번만 순회할 수 있는 객체로, 순회(iteration)에 특화된 자료형입니다.

✔ list(product(...))를 사용하면 한 번에 모든 데이터를 메모리에 담아 여러 번 사용 가능
✔ product(...) 그대로 사용하면 메모리를 절약할 수 있지만 한 번만 순회 가능

from itertools import product

def generate_cases(n):
    choices = ['A', 'B', 'C', 'D']  # 4가지 선택지
    cases = list(product(choices, repeat=n))
    return ["".join(case) for case in cases]

n = 3  # 예시로 n=3
cases = generate_cases(n)

for case in cases:
    print(case)

코드

from itertools import product
def solution(users, emoticons):
    answer = []
    discount_per = [10,20,30,40]
    total_money = 0
    plus_members = 0
    reulst_case = []
    cases=list(product(discount_per, repeat =len(emoticons)))

    for case in cases:
        temp_total = 0 #케이스 별 총 액수
        temp_member_count =0 #케이스 별 가입 수
        for user in users:
            sum_emo=0 # 유저가 지불한 금액 총액
            standard_dis = user[0]
            # 각 유저 구매한 총액 계산
            for i in range(len(case)):
                if case[i] >= standard_dis:
                    sum_emo += emoticons[i]*(1-(case[i]/100))
            # 플러스 가입 유무 판단
            if sum_emo >= user[1]:
                temp_member_count = temp_member_count + 1
            else:
                temp_total = temp_total + sum_emo
        # 이전결과보다 좋은지 판단
        if plus_members < temp_member_count:
            plus_members = temp_member_count
            total_money = temp_total
            reulst_case = case
        elif plus_members == temp_member_count:
            if temp_total > total_money:
                total_money = temp_total
                reulst_case = case

    return [plus_members, total_money]