본문 바로가기

환영합니다. 이 블로그 번째 방문자입니다.
Python/문제풀이

[2021 KAKAO 블라인드 채용] 메뉴 리뉴얼

👇🏻 문제

https://programmers.co.kr/learn/courses/30/lessons/72411

 

코딩테스트 연습 - 메뉴 리뉴얼

레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서

programmers.co.kr


이 문제로 정말 애를 좀 먹었다. 로직은 대충 알겠는데 막상 구현에서 쩔쩔맸다. 그 이유는 다음과 같다.

 

조합을 구현하는데에 무한 loop 에 빠졌다. 재귀함수 잘못 짠...

 

파이썬에 combinations가 있었던 걸 알았다면, 더 편하게 짰을 것 같다.

 

나의 로직은 다음과 같다.

1. course의 반복문을 돌며 orders의 원소들을 일일히 검사한다.

2. course보다 orders 원소의 길이가 길 때만 검사를 하며, orders 원소는 리스트 형태로 변환해 정렬을 먼저 해준다. (테스트 3번의 예외를 잡아주기 위해서)

3. course의 개수대로 orders 원소를 조합하고 comb_list가 비어있다면 그대로 배열에 삽입한다. (nCr)

4. comb_list가 비어있지 않으면 새로운 orders 원소 조합이 comb_list에 있는지 확인한 다음, 없으면 추가하고 있으면 find_comb에 추가한다. 

5. find_comb에 있으면 카운트를 증가시켜주고 없으면 카운트 = 2(이미 들어있던 것 + 새로 들어온 것도 있을 경우이므로)으로 추가해준다.

6. find_comb 가 비어있지 않을 경우, 가장 큰 카운트 value 를 가지고 있는 key를 찾아 answer에 추가해준다.

7. answer을 오름차순으로 정렬해준다.


👇🏻 코드

 

from itertools import combinations

def solution(orders, course):
    answer = []

    for length in course:
        comb_list=[]
        find_comb={}

        for order in orders:
            if len(order) >= length:
            
                order_list = list(order)
                comb_list.sort()
                order_list.sort()

                if len(comb_list) == 0: comb_list += [list(elem) for elem in list(combinations(order_list,length))]
                else:
                    for elem in list(combinations(order_list,length)):
                        if list(elem) in comb_list:
                            string=''
                            for e in list(elem):
                                string += str(e)
                            if string in find_comb: find_comb[string] += 1
                            else: find_comb[string] = 2
                        else: 
                            comb_list.append(list(elem))

        if find_comb:
            max_value = max(find_comb.values())
            for key in find_comb:
                if max_value == find_comb[key]:
                    answer.append(key)
            
    answer.sort()
    return answer

orders=["XYZ", "XWY", "WXA"]
course=[2,3,4]

solution(orders,course)