2023 카카오 코테 기출 - 이모티콘 할인행사

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

나의 풀이

접근

먼저 할인율이 10, 20 ,30 ,40으로 4가지 밖에 존재하지 않는다는 점과, 이모티콘의 갯수 m또한 최댓값이 7밖에 되지 않는 다는 점에서 먼저 bruteforce 방식을 떠올렸다.

중복 순열을 적용하여 [10,10,10...10] 부터 [40,40,40,....40] 까지의 배열이 존재하는 튜플을 하나 생성하고 튜플 안에 존재하는 각각의 배열들을 하나씩 순회하면서 각각의 경우의 수 마다 가입수와 가격을 비교해가며 갱신해줌

코드

from itertools import product
def solution(users, emoticons):
    answer_count=-1
    answer_total=-1
    
    sale_list=[10,20,30,40]
    emot_permu=product(sale_list,repeat=len(emoticons))
    
    for emot in emot_permu:
        # emot 은 각각의 세일율
        count=0  # 토탈 가입 수
        total=0  # 토탈 가격
        for user in users:
            user_total=0
            for i in range(len(emoticons)):
                if emot[i]>=user[0]:
                    user_total+=((emoticons[i]*(100-emot[i]))//100)
            if user_total>=user[1]:
                count+=1
            else:
                total+=user_total
        if count>answer_count:
            answer_count=count
            answer_total=total
        elif count==answer_count and total>answer_total:
            answer_total=total
    return [answer_count,answer_total]

추가

중복 순열 라이브러리가 기억나지 않아 시간을 많이 쓰게 되었고, 결국 product 함수를 찾기 위해 구글링하였다.
하지만 실제 시험 상황에서는 구글링을 할 수 없기 때문에 스스로 중복 순열 함수 기능을 구현해보자 한다.

내 구현

import copy

answer_list=[]
def make_prdocut(answer,num_list,n,m):  # num_list는 할인율 배열, n은 중복순열의 길이 answer은 만들어진 순열 n은 탈출 조건 m은 emoticon 길이
  
  if n==m:
    answer_list.append(answer)
    return
  for num in num_list:
    temp=copy.deepcopy(answer)
    temp.append(num)
    make_prdocut(temp,num_list,n+1,m)

다른 구현

def make_percentage_cases(prev):
    cases = []
    for li in prev:
        for n in [40, 30, 20, 10]:
            cases.append(li + [n])
    return cases

def solution(users, emoticons):
    answer = []

    cases = [[]]  # 가능한 이모티콘별 할인율 케이스들
    for _ in range(len(emoticons)):
        cases = make_percentage_cases(cases)

처음 결과

두번쨰 결과

데이터가 커질수록 함수 구현이 속도가 좀 더 빠른 것을 확인 할 수있다. 근데 뭐 비슷한듯 이런 문제 나오면 그냥 product ㄱㄱ