[프로그래머스] 메뉴리뉴얼 .py

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

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

 

from collections import Counter
from itertools import combinations

def solution(orders, course):
    answer = []
    
    for length in course:
        order_list = []
        for order in orders:
            for combi in combinations(order, length): # length의 길이만큼 모든조합 찾기
                order_list.append(''.join(sorted(combi)))
                
        if order_list: #order_list가 없는 경우를 주의
            order_list = Counter(order_list).most_common()

            for word, cnt in order_list:
                if cnt > 1 and cnt == order_list[0][1]: # max_count 반환
                    answer.append(word)
                else:
                    break 
                    # most_common()순으로 정렬해주었으므로 같지않으면 뒤는 max_count보다 작다.
        
    return sorted(answer)

처음에 combinations과 counter을 생각했지만, 둘 다 써버리면 보통 시간초과가 나는 경우가 많으므로

당연히 아닐줄알고 dictionary로 방향을 바꿨었다. dict로 푸는 도중 뭔가 이상하다고 느껴 다시 원래 접근방식으로 풀었더니 정답이었다.

 

 

combinations과 counter을 써도 시간초과가 나지 않는 이유는, 지극히 적은 범위 때문.

중복도 허용하지 않으므로 써 줄 수 있었다.