🐹 이모티콘 할인 행사

1. 문제 링크

2023 KAKAO BLIND RECRUITMENT: 이모티콘 할인 행사

2. 코드

from itertools import product

def solution(users, emoticons):
    answer = [0, 0]
    u_num = len(users)
    e_num = len(emoticons)
    discount_rate = [40, 30, 20, 10]
    # 이모티콘 개수만큼 뽑는 모든 중복 순열 구하기(이모티콘 할인율 모든 경우 구하기)
    for d_list in product(discount_rate, repeat=e_num):
        purchase_history = [0] * u_num
        now = [0, 0]    # 플러스 가입자, 판매액
        for i, d in enumerate(d_list):
            for j in range(u_num):
                # 유저가 원한 할인율보다 높으면(구매 조건 충족)
                if users[j][0] <= d:
                    purchase_history[j] += emoticons[i] * (100 - d) // 100
        # 이모티콘 플러스 가입자 확인
        for i in range(u_num):
            # 이모티콘 구매 비용이 본인 일정 가격 이상 -> 이모티콘 플러스 가입
            if users[i][1] <= purchase_history[i]:
                now[0] += 1
            # 플러스 가입자 아닐때 -> 판매액 산정
            else:
                now[1] += purchase_history[i]
        # 1순위: 이모티콘 플러스 가입자
        if answer[0] < now[0]:
            answer = now
        # 2순위: 판매액
        elif answer[0] == now[0] and answer[1] < now[1]:
            answer = now
    
    return answer

• 정확성

  테스트 1 〉	통과 (0.05ms, 10.2MB)
  테스트 2 〉	통과 (0.10ms, 10.2MB)
  테스트 3 〉	통과 (0.45ms, 10.3MB)
  테스트 4 〉	통과 (2.02ms, 10.3MB)
  테스트 5 〉	통과 (3.68ms, 10.2MB)
  테스트 6 〉	통과 (2.38ms, 10.2MB)
  테스트 7 〉	통과 (20.09ms, 10.2MB)
  테스트 8 〉	통과 (10.82ms, 10.2MB)
  테스트 9 〉	통과 (91.58ms, 10.2MB)
  테스트 10 〉	통과 (50.08ms, 10.3MB)
  테스트 11 〉	통과 (451.38ms, 10.3MB)
  테스트 12 〉	통과 (251.42ms, 10.4MB)
  테스트 13 〉	통과 (1973.12ms, 10.4MB)
  테스트 14 〉	통과 (1805.55ms, 10.2MB)
  테스트 15 〉	통과 (87.65ms, 10.2MB)
  테스트 16 〉	통과 (85.70ms, 10.2MB)
  테스트 17 〉	통과 (0.44ms, 10.3MB)
  테스트 18 〉	통과 (29.05ms, 10.2MB)
  테스트 19 〉	통과 (0.09ms, 10.2MB)
  테스트 20 〉	통과 (0.06ms, 10.2MB)

3. 해설

이모티콘에 모든 할인율을 부여하여 모든 경우의 수를 따져 가장 최선의 선택을 뽑는다.

중복순열을 통해 가능한 모든 할인의 경우를 계산하고 그때의 모든 결과(플러스 가입자, 판매액)을 비교해준다.

이때 시간복잡도를 대략 계산해봤을 때 최악의 경우 이모티콘 개수 = 7, 유저 수 = 100이고, 이모티콘 할인율 4개로 계산을 했을 때 모든 경우를 구하는 시간은 아래와 같고, 모든 경우를 다 구해도 1초에 1억번 계산이 가능하다고 한다면 총 1억번 이하이므로 모든 경우를 탐색해도 된다.

\[4^7 * 100 = 2^{14} * 10^2 = 2^{10} * 2^4 * 10^2 \fallingdotseq 10^3 * 16 * 10^2 = 1.6 * 10^6\]

유저별 최종 구매내역을 구한 후 일정 가격 이상은 플러스 가입자에 더해주고, 아닌 경우 판매액에 더한 후 최종 값을 max값과 비교하여 변경해준다.