[프로그래머스/파이썬] Level 2 메뉴 리뉴얼

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

---

문제풀이

처음에는 다음과 같이 접근했다.
orders에 포함된 알파벳들중 course에 따른 조합을 구해주고 해당 조합의 값마다 check함수를 돌려주었다. check함수는 orders, order를 돌면서 해당 조합이 order에 포함되어 있고 최소 2명 이상에 포함된 경우의 수만 리턴해주었다.

그리고 각 course개수에 따라 가장 많이 주문된 메뉴 조합을 구하고 사전 순으로 오름차순해서 출력해주었다.

결과는 3개의 케이스에서 시간초과가 발생했다..
모든 경우의 수를 구해서 계산하는 과정에서 시간이 많이 걸린 것 같다.

틀린코드

from itertools import combinations

def solution(orders, course):
    alphabet=[]
    max_len=0
    for i in orders:
        if len(i)>=max_len:
            max_len=len(i)
        for j in i:
            if j not in alphabet:
                alphabet.append(j)
    alphabet.sort()
                
    def check(a):
        temp=[]
        for order in orders:
            cnt=0
            for i in a:
                if i in order:
                    cnt+=1
                if cnt>=len(a):
                    temp.append("T")
                    break
        if len(temp)>=2:
            return len(temp)
    
    result=[]
    for num in course:
        if num>max_len:
            break
        array=list(combinations(alphabet,num))
        lst=[]
        for i in array:
            if check(i):
                lst.append((check(i),i))
        lst.sort(reverse=True)
        max_length=0
        for i in lst:
            length,menu=i
            if length>=max_length:
                result.append("".join(menu))
                max_length=length
            else:
                break

    result.sort()
    return(result)

Counter객체를 활용해서 course에 따라 orders, order를 돌며 주문된 횟수를 구해준다.

most_common()는 데이터의 개수가 많은 순서대로 리스트를 리턴해준다.

해당 리스트에서 최소 2명 이상의 손님에게서 주문된 구성, 가장 많이 주문된 구성만 결과 리스트에 포함해준다.

소스코드

from collections import Counter
from itertools import combinations

def solution(orders, course):
    
    result=[]
    for num in course:
        array=[]
        for order in orders:
            for value in combinations(order,num):
                array.append("".join(sorted(value)))
    
        if array:
            array=Counter(array).most_common()
            for w,c in array:
                if c>=2 and c==array[0][1]:
                    result.append(w)
                else:
                    break
    
    return sorted(result)