[프로그래머스] No.72411 메뉴 리뉴얼 01

 

프로그래머스

백준과 프로그래머스를 병행하면서 문제를 풀다가 도달한 문제다.

이번 문제는 이해하는 게 조금 난해했다.

"코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다."...? 라고 하는 게 이해가 안 됐다.

아니 정확하게는 '코스 요리는 2글자 이상이어야 한다'는 알겠다.

하지만 여러 개의 코스 요리가 나오는데, 어떤 기준으로 메뉴를 선택하는 거지?

코딩테스트 문제에서 풀이 과정을 얻을 수 있지만, 예제에서 얻는 문제도 있다고 한다.

하지만 아무리 그래도... 문제를 보고 풀 수 있어야 문제가 아닌가 싶기는 하다.

그래도 우선 해봐야 무엇이 틀렸는지, 확인할 수 있으니 풀어보기로 했다.

 

가장 좋은 확인 방법은 예제 풀이를 해 준 경우를 내가 따라가는 것이다.

우선 6명의 손님이 주문한 모든 메뉴의 개수를 세어서 오른쪽의 표를 만들어봤다.

가장 먼저 든 생각은 '모든 메뉴가 2번 이상 시켰다면 세트로 만들라는 소리인가?'였다.

 

예를 들자면, 2번 손님은 A와 C를 주문했다.

이때 오른쪽 표를 보면 A와 C는 모두 2번 이상 주문한 메뉴이다.

그럼 AC를 세트 메뉴로 만들어야 하는 것인가?라는 뜻이다.

 

def count_alphabet(count_dict, word):
    for w in word:
        count_dict[w] = count_dict.get(w, 0) + 1
    return count_dict

그래서 알파벳의 개수를 세는 함수를 만들어 따로 세기로 했다.

간단하게 count_dict에서 get을 이용해서 개수를 세는 함수다.

 

def solution(orders, course):
    answer = []
    dict_ = {}
    
    for order in orders:
        dict_ = count_alphabet(dict_, order)
    
    for order in orders:
        for o in order:
            if dict_[o] < 2:
                break
        else:
            answer.append(order)
    
    return sorted(answer)

첫 번쨰 반복문에서 모든 알파벳 개수를 센다.

두 번째 반복문에서 각 order의 한 글자 한 글자를 돌면서 2개를 넘었나 확인한다.

넘었다면 answer에 세트 메뉴를 추가한다.

 

음 역시나 아니다.

잘 살펴보니까 1번 예제에서는 H만이 2번 이상 주문한 메뉴가 아니다.

즉 ABCFG도 위의 코드에 의하면 answer에 포함되는 메뉴라는 것이다.

하지만 아니다. 조금 더 깊게 생각할 필요가 있다.

 

거꾸로 생각을 해보자. 요리 2개 코스, 3개 코스, 4개 코스는 여러 개 있는데 왜 하필 쟤네만 해당할까?

2개부터 생각해보자. AB부터 EH까지 다양하게 된다.

GH가 아닌 이유는, 어떤 손님에도 G와 H를 동시에 주문한 손님은 없기 때문이다.  

전제 조건은 손님이 주문한 메뉴에서 조합해야 한다는 것이다.

1번 손님, AB, AC, AF, AG, BC, BF, .... 아 혹시?

혹시 말그대로 조합(combinations)을 물어보는 문제는 아닐까?

각 손님들이 가능한 모든 조합을 세서, 길이마다 가장 많은 주문을 세트 메뉴로 만드는 건 아닐까?

이게 시간이 되려나? 시간복잡도를 초과하지는 않을까?

 

최악의 크기를 생각해보자. 그것이 Big-O 표기법이니까.

orders의 배열의 크기는 20, 즉 최대 주문은 20개가 들어온다.

각 order는 최대 10개의 문자열로 이루어져있다.

10개의 문자에서 2개까지 세트 메뉴, 3개까지 세트 메뉴, ..., 10개짜리 세트 메뉴가 나올 수 있다.

10개에서 N개를 뽑아 조합하는 경우의 수는 파스칼의 삼각형을 이용하면 쉽게 구할 수 있다.

10C2, 10C3, 10C4, ..., 10C9, 10C10으로 파스칼의 삼각형 11번째 줄에 해당한다.

45 + 120+ 210 +252 + 210 + 120 + 45 + 10 + 1으로 1013가지다.

20개의 메뉴는 각 1013가지의 가능성을 가지고 있으므로, 가능한 모든 경우는 20260가지.

아 2만개뿐이라면 충분히 모든 경우의 수를 탐색해도 가능하겠구나 생각했다.

 

answer = [[] for _ in range(11)]

for c in course:        
    for order in orders:
        combi = combinations(sorted(order), c)
        answer[c].append(*combi)

answer를 11개의 빈 리스트로 생성해 세트 메뉴 길이를 index로 활용하려고 했다.

11개로 선언한 이유는 index를 1부터 세서, 편하게 계산하기 위해서다.  

몇 개를 묶어서 세트 메뉴를 만들지에 대한 길이 정보는 course 리스트에 들어있다.

각 정보에 대해서 순서대로 들어온다는 보장이 없으니, 정렬을 한 번 해줘야 한다.

그리고 course의 각 요소만큼 세트 메뉴를 조합(combinations)한다.

 

이러다보니 한 가지 문제점이 생겼다. 개수를 파악할 수 없다는 거다.

개수를 파악하기 위해서는 dict로 세트 메뉴를 key, 개수를 value로 가져가야 하나?

그럼 또 코드가 복잡해지는데? 라는 생각이 들었다.

외부 라이브러리를 사용하지 않는 선에서, 적재적소에 라이브러리 사용은 약(藥)이라는 생각을 했다.

실제로 빠른 입력을 위해 sys도 사용하고, BFS를 위해 deque도 사용한다.

당장 이 문제에서만 해도 조합을 위해 itertools의 combinations을 사용하고 있다.

따라서 collections의 Counter 라이브러리를 사용하기로 했다. 

 

from itertools import combinations
from collections import Counter

이 문제에서 사용할 라이브러리를 크게 2가지다. combinations과 Counter.

combinations은 iterable 객체와 int를 매개변수로 갖는다.

iterable 객체에 대해서 int 개수만큼 가능한 모든 조합의 경우의 수를 반환한다.

Counter는 iterable 객체 하나를 매개변수로 갖는다.

iterable 객체에 대해서 element를 key로 개수를 value로 취급해 dictionary 형태로 반환한다.

 

def solution(orders, course):
    answer = []
    
    for c in course:
        temp = []
        
        for order in orders:
            combi = combinations(sorted(order), c)
            temp += combi

course의 세트 메뉴 길이(c)에 대해서 하나씩 돌아준다.

그리고 각 길이에 대해서 모든 손님의 주문(order)에 대해 조합(combinations)을 실행한다.

그리고 temp에 더해준다.

그럼 모든 손님에게 발생하는, 각 조합의 경우의 수가 temp에 들어간다. 

course에 2, 3, 4가 들어있다면, 첫 번째 반복문에서는 2가지 를 묶은 세트 메뉴, 다음에는 3가지를 묶은 세트가 들어간다.

 

    counter = Counter(temp)

    if len(counter) == 0 or max(counter.values()) == 1:
        continue

    MAX = max(counter.values())
    answer += [''.join(c) for c, t in counter.items() if t == MAX]

return sorted(answer)

Counter를 사용해 temp를 Counter 객체로 만들어 counter에 담는다.

만약 counter에 세트 메뉴가 하나도 없거나, 최대로 주문한 횟수가 1이라면, 다음 세트 메뉴를 확인하러 간다.

예를 들어 counter = {"AB" : 1, "BC" : 1, "AG" : 1}이라면, 2가지를 묶은 세트 메뉴는 만들지 않는다.

그러니 3가지를 묶은 세트 메뉴를 확인하러 간다.

그게 아니라면 values 중에서 가장 큰 값(주문이 많은 메뉴=MAX)를 확인한다.

counter의 모든 요소를 돌면서 주문이 MAX라면, answer에 추가해준다.

그리고 마지막으로 모든 answer를 한 번 더 정렬해준다.

문제 조건에서 각 세트 메뉴도 오름차순 정렬이지만, 전체 메뉴도 오름차순 정렬이라고 한다.

 

그랬더니 꽤나 안정적으로 AC를 받을 수 있었다.

어째 문제를 풀수록 내가 컴퓨터 공학과가 아니고, 국문과나 영문과나 수학과는 아닐까?라는 생각이 든다.

다양한 능력을 요구한다는 이야기이니, 다양하게 공부하자.