[코딩테스트] 2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼 문제

kysung95·2021년 5월 6일

코딩테스트

목록 보기

4/10

안녕하세요. 김용성입니다.
오늘은 2021 KAKAO BLIND RECRUITMENT 코딩테스트 2번 메뉴 리뉴얼 문제를 풀어보도록 하겠습니다.
풀고나서 후기를 살펴보니 이 문제에서 시간을 허비하신 분들이 정말 많더군요.
단순하게 생각하고 풀어버리는 것이 중요했다고 생각합니다.

문제

2021 KAKAO BLIND RECRUITMENT 2번 문제 링크

문제 설명
레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.
기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 "스카피"는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다.
단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다.

예를 들어, 손님 6명이 주문한 단품메뉴들의 조합이 다음과 같다면,
(각 손님은 단품메뉴를 2개 이상 주문해야 하며, 각 단품메뉴는 A ~ Z의 알파벳 대문자로 표기합니다.)

손님 번호 주문한 단품메뉴 조합
1번 손님 A, B, C, F, G
2번 손님 A, C
3번 손님 C, D, E
4번 손님 A, C, D, E
5번 손님 B, C, F, G
6번 손님 A, C, D, E, H
가장 많이 함께 주문된 단품메뉴 조합에 따라 "스카피"가 만들게 될 코스요리 메뉴 구성 후보는 다음과 같습니다.

코스 종류 메뉴 구성 설명
요리 2개 코스 A, C 1번, 2번, 4번, 6번 손님으로부터 총 4번 주문됐습니다.
요리 3개 코스 C, D, E 3번, 4번, 6번 손님으로부터 총 3번 주문됐습니다.
요리 4개 코스 B, C, F, G 1번, 5번 손님으로부터 총 2번 주문됐습니다.
요리 4개 코스 A, C, D, E 4번, 6번 손님으로부터 총 2번 주문됐습니다.
[문제]
각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

[제한사항]
orders 배열의 크기는 2 이상 20 이하입니다.
orders 배열의 각 원소는 크기가 2 이상 10 이하인 문자열입니다.
각 문자열은 알파벳 대문자로만 이루어져 있습니다.
각 문자열에는 같은 알파벳이 중복해서 들어있지 않습니다.
course 배열의 크기는 1 이상 10 이하입니다.
course 배열의 각 원소는 2 이상 10 이하인 자연수가 오름차순으로 정렬되어 있습니다.
course 배열에는 같은 값이 중복해서 들어있지 않습니다.
정답은 각 코스요리 메뉴의 구성을 문자열 형식으로 배열에 담아 사전 순으로 오름차순 정렬해서 return 해주세요.
배열의 각 원소에 저장된 문자열 또한 알파벳 오름차순으로 정렬되어야 합니다.
만약 가장 많이 함께 주문된 메뉴 구성이 여러 개라면, 모두 배열에 담아 return 하면 됩니다.
orders와 course 매개변수는 return 하는 배열의 길이가 1 이상이 되도록 주어집니다.

풀이

일단 문제 자체를 이해하는데에 시간이 좀 오래걸렸던 것 같아요. 그렇지만 이해하고 나니 떠오르는 것이 딱 두가지 있더군요. 바로 조합과 카운터였어요. 문자열의 모든 조합을 구해서 최빈순으로 나열하고 적어도 1회 이상 출력되는 것들에 한해서만 리턴해주면 되는 문제더라구요. 오히려 이 문제에서 시간이 오래걸리셨다 하는 분들은 효율성에 신경을 많이 쓰신 것 같은데, 여기서 키포인트는 orders와 course의 최대 입력값이 그리 크지 않다는 점이예요. 그렇기 때문에 시간초과를 걱정하지 않고 떠오르는 모듈을 사용해서 접근한다면 쉽게 풀 수 있던 문제라고 생각합니다.

course만큼의 반복문 생성

처음 반복문을 설계할 때 고민을 했었는데 생각해보니 결국은 2개짜리 메뉴 어떤거 어떤거, 3개짜리 메뉴 어떤거 어떤거 이런식으로 나열하면 되는것이기에 course의 요소들로 반복문 틀을 잡고 시작했어요.
그리고 combinationArray라는 리스트를 하나 생성해서 course 반복문을 한번 돌 때마다 채우고 비워주고를 반복하면서 counter를 돌려주게끔 설계하였습니다.

  for c in course:
        combinationArray=[]

sorted의 중요성

테스트 케이스 3번째를 보면 손님들이 알파벳 순서로 주문을 하지 않았다는 점이 보입니다.
이러한 상황을 대비해서 조합을 돌릴 때에는 무조건 sorted로 order객체를 감싸주어야 했어요. 왜냐하면 문제에서 기대값들을 보면 모두 다 알파벳 순 정렬이 되어있기 때문이죠.

for order in orders:
            combinationArray+=list(combinations(sorted(order),c))

counter를 잘 다뤄보기

저는 counter 모듈에 익숙치 않아서 이 부분에서 시간을 좀 잡아먹었는데요. 2019년도에 나왔던 카카오의 튜플 문제가 있어요. 해당 문제에서도 counter를 사용하면 쉽게 풀 수 있다는 점 알고 계신가요?
제 생각에는 카카오 1,2 문제를 풀 때 counter에 대해 잘 알고 있다면 분명 도움이 될 것이라 생각합니다.
또한 counter 자체의 most_common()이라는 메소드를 사용하면 빈도수와 더불어서 딕셔너리 형태로 리스트를 만들어주기 때문에 시간 복잡도에서 이득을 볼 수 있는 경우가 분명 생길 것이라고 생각해요. (딕셔너리의 시간 복잡도가 상당히 좋더라구요.)

지금 위에서 만든 for문에서 나오는 combination array를 counter를 사용하여 정리하면 각각 빈도수에
따라서 정렬되어서 나옵니다.

//테스트 케이스 1번의 2개 조합의 counter

c= 2 Counter({('A', 'C'): 4, ('C', 'D'): 3, ('C', 'E'): 3, ('D', 'E'): 3, ('B', 'C'): 2, ('B', 'F'): 2, ('B', 'G'): 2, ('C', 'F'): 2, ('C', 'G'): 2, ('F', 'G'): 2, ('A', 'D'): 2, ('A', 'E'): 2, ('A', 'B'): 1, ('A', 'F'): 1, ('A', 'G'): 1, ('A', 'H'): 1, ('C', 'H'): 1, ('D', 'H'): 1, ('E', 'H'): 1})

이런식으로 나온 counter 맵 중에서 우리가 필요한 것은 바로 가장 빈도수가 높은 것, 즉 ['A','C']가 필요한 것이죠. 저것을 추출할 때 저는 다음과 같이 진행하였습니다.

join 활용

 answer+=[''.join(k) for k, v in combinationArray.items() if v == max(combinationArray.values()) and v>1]

코드가 좀 긴 것 같은데요. 컴프리헨션을 사용하였습니다.
저렇게 나온 값들 중에서 가장 values(여기서는 빈도수가 되겠죠?)가 가장 큰 값들을 출력하되 그 값들이 여러개 있다면 모두 answer에 더해줄 수 있게 했고, 단 2명 이상이 주문을 했어야한다는 조건을 지키기 위해서 value값이 1보다는 무조건 크게 잡아주었습니다. (이 작업을 하지 않는다면 테스트케이스 2번,3번에서 실패합니다.)

최종 코드

from itertools import combinations
from collections import Counter

def solution(orders, course):
    answer = []
    
    for c in course:
        combinationArray=[]
        for order in orders:
            combinationArray+=list(combinations(sorted(order),c))
        combinationArray=Counter(combinationArray)
        print("c=",c,combinationArray) # 이해하시는데 도움이 되실겁니다.
        answer+=[''.join(k) for k, v in combinationArray.items() if v == max(combinationArray.values()) and v>1]
    
    return sorted(answer)