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

오늘은 날씨가 너무 좋았지만 수업이 너무 많아 밖에 나가지도 못했다...😥

 

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

 매번 느낀 게 카카오 문제는 너무 귀엽다! 보통 민수, 철수 이런 식으로 예시가 나오는데 여기는 스카피, 콘, 피치 등등 귀여운 이름으로 나온다 

 

특히 '레스토랑을 운영하던 스카피는 코로나 19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다.' 이런 문구가 나오면 진짜로 내가 스카피의 문제를 해결해줘야 할 것 같다ㅎㅎㅎ

 

스카피의 문제를 해결해주자!!!!!!!!😤

 

문제 설명

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

 

해당 문제는 입출력 예만 보면 쉽게 이해가 가능하다.

orders	course	result
["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"]	[2,3,4]	["AC", "ACDE", "BCFG", "CDE"]
["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"]	[2,3,5]	["ACD", "AD", "ADE", "CD", "XYZ"]
["XYZ", "XWY", "WXA"]	[2,3,4]	["WX", "XY"]

해당 입출력 예처럼 orders에서 리스트 문자열 원소에서 course의 원소의 값만큼 문자열을 뽑고 해당 문자열의 숫자를 세어 각 course(문자열의 길이)에서 가장 큰 값을 result 하는 것이다.

추가로 이 문제는 제한사항이 굉장히 많다 문제를 보고 하나하나 따져보는 게 좋다.

 

맨 마지막의 예시를 문제로 적용하자면

"XYZ"->XY, XZ, YZ (course 2)/ XYZ(course 3)

"XWY"->XW, XY, WY (course 2)/ XWY(course 3)

"WXA"->WX, WA, XA (course 2)/ WXA(course 3)

 

XY->2 XZ ->1 YZ->1 WX->2(XW==WX) WY->1 WA->1 XA->1 

XYZ->1 XWY->1 WXA->1

 

result->WX, XY

이런 식으로 적용되는 것이다. 여기서 왜 XYZ, XWY, WXA는 왜 안 들어가지?라고 의문을 가질 수 있다.

그런데 문제를 잘 읽어보면 중요한 조건이 하나 있다.

최소 2명 이상의 손님으로부터 주문한 단품 메뉴 조합에서만 후보에 포함하기로 한다.

그렇다는 건 XYZ, XWY, WXA 다 한 명에게 주문된 거라 result가 될 수 없다.

 

풀이 방법

 orders의 리스트 안 문자열을 오른 차순으로 만들고 course 리스트 원소 값에 맞춰 조합을 적용시켰다.

조합한 내용을 딕셔너리에 넣고 만약 중복일 경우에는 빈도수(values)+1을 적용시켰다.

그 후 딕셔너리에 문자열의 길이로 정렬을 하고 문자열 길이 별로 가장 큰 빈도수를 answer에 저장하고 오른 차순으로 정리했다.

왜?

 해당 문제를 읽자마자 첫 번째 orders의 배열 문자열이 오름차순이 아니네 라는 생각 두 번째 주어진 배열의 크기가 크지 않아서 조합으로 다 돌아야겠다는 생각이 들었기 때문이다.

 

코드

import itertools
def solution(orders, course):
    #배열의 크기가 생각보다 크지 않음. 다 도는게 맞다고 생각.
    answer = []
    d={}    
    order=[]
    setence=""
    standard=[0]*11
    
    for i in orders:#주어진 부분을 다 정렬하는 것. ["AVD","ED"]->["ADV","DE"]
        i=list(i)  
        i.sort()# 값을 정렬하기 위해서 배열에 모아서 정렬하고
        for j in i:
            setence+=j#str로 만들어서 
        order.append(setence)
        setence=""# 값 리셋

    for i in order:
        for j in course:
            nCr = list(map(''.join ,itertools.combinations(i, j)))#조합을 통해 dict 생성.
            for k in nCr:
                if k in d.keys():#만약 이전에 있던 값이 있으면+1
                    d[k]=d[k]+1
                else:#없으면 dict에 추가하고 1로 세팅.
                    d[k]=1
                    
    res=sorted(d.items(),key=(lambda x:x[1]),reverse=True)#크기 순서대로 정렬. 5, 4, 3 ,2 ,1 ....
    
    for i in res:#찾고로 여기서 i[1]은 dict의 value의 값을 말함.
        if i[1]==1:#이게 어떤 메뉴든 2이상이 아니면 추가 못함.조건에 보면 있음.
            break
        if standard[len(i[0])]<=i[1]:#standard라는 배열이 있는데 course별로 가장 큰 값을 가지는 keys를 찾아서 answer에 넣어둠.
            standard[len(i[0])]=i[1]#기준 값을 변경 
            answer.append(i[0])    
        #elif standard[len(i[0])]==i[1]:#가장 큰 값의 key의 value랑 같은 값이면 그 값도 answer에 넣기.
         #   answer.append(i[0])    
    
    answer.sort()# sort!!
    
    return answer

 

실행 결과

원래 python에서 딕셔너리 자료형을 잘 몰랐는데 조금 알게 된 느낌이다!!

많이 많이 풀어보자🤗