[알고리즘] 메뉴 리뉴얼

프로그래머스 2021 KAKAO BLIND RECRUITMENT 코딩테스트에서 출제된 문제
메뉴 리뉴얼 문제

분석

모든 조합을 구하고 중복의 개수가 최대이면 답에 추가하는 방식으로 진행하였다.

1.모든 경우

for j in orders: tmp+=list(combinations(j,i))

모든 경우를 넣기 위해서 주어진 order의 수만큼 조합을 만든다.

2.중복 체크

for j in tmp:
      try: menu[j]+= 1
      except: menu[j]=1

모든 경우를 만들었기 때문에 중복된 조합이 몇개 있는지 체크한다.

3.두번 이상이면 진행

n개의 메뉴중에 최대값이 2이상이면 진행한다.(최대값이 1이면 중복된 조합이 없다는 뜻이므로 진행하지 않는다)

maxN = max(menu.values())
if maxN>=2:
	for j in menu:
		if maxN == menu[j]: 
			answer.append(''.join(j))

모든 조합 종류를 탐색하여 최대값과 같으면 답에 append한다.

4.순서 문제

처음 orders에서 주어진 문자열 순서가 달라서 메뉴 추출한 결과가 다른 문제가 발생했다. 이러면 다른 메뉴로 인식해버리기 때문에 답에 포함되지 않는다.

for i in range(len(orders)): 
    	orders[i] = sorted(list(orders[i]))

orders의 메뉴들을 하나씩 정렬하여 뒤의 메뉴 추출에 문제가 되지 않도록 하였다.

코드

from itertools import combinations

def solution(orders, course):
    answer = []
    for i in range(len(orders)): 
    	orders[i] = sorted(list(orders[i]))
        
    for i in course:
        tmp, menu = [], {}
        for j in orders: tmp+=list(combinations(j,i))
        for j in tmp:
            try: menu[j]+= 1
            except: menu[j]=1
        try: 
            maxN = max(menu.values())
            if maxN>=2:
                for j in menu:
                    if maxN == menu[j]: 
                        answer.append(''.join(j))
        except: continue
    answer.sort()
    return answer