파이썬 알고리즘 247번 | [프로그래머스 메뉴 리뉴얼] - 설명 주석

Yunny.Log ·2022년 8월 19일

Algorithm

목록 보기

252/318

1) 어떤 전략(알고리즘)으로 해결?

사전, 문자열 처리

2) 코딩 설명

<내 풀이>


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

from itertools import combinations

def solution(orders, course):
    answer = []
    dict = {}
    length_cmp = {}
    total = {}

    for c in course :  
        length_cmp[c] = 0 
        # 길이 분류 , course 가 2,3,4 면 {2: 0, 3:0, 4: 0}
        # 각 길이 중 가장 많이 나온 최대 갯수 담을 거임
        # 예시 1의 경우 :{2: 4, 3:3, 4: 2}

        total[c] = [] 
        # 길이 분류 , course 가 2,3,4 면 [2:, 3:, 4:]
        # 여기다가는 각 길이 최대 갯수에 해당하는 조합 집어넣을 것임
        # {2: ['AC'], 3: ['CDE'], 4: ['BCFG', 'ACDE']}

    for order in orders : # 한 사람당 한 주문 
        order = list(order)
        order.sort() # 오름차순 정렬 해줘야 함 

        if len(order) > 1 : 
            for i in range(len(course)) : 
                # 코스 길이에 해당하는 만큼 조합 구하기
                comb = combinations(order, course[i])
                    
                for co in comb : 
                    # 조합을 키 값으로 해서 사전에 없으면 추가 
                        if "".join(co) in dict : 
                            dict["".join(co)]+=1
                        else : 
                            dict["".join(co)] = 1
    # print(dict)
    # {'XY': 2, 'XZ': 1, 'YZ': 1, 'XYZ': 1, 'WX': 2, 'WY': 1, 'WXY': 1, 'AW': 1, 'AX': 1, 'AWX': 1}

    for di in dict :
        # dict[di] 는 내가 뽑혔던 갯수 
        # 두번 이상 뽑혀야 하고 && 최대 갯수여야 함 

            # 만약 두번이상 뽑혔고, 지금 내가 뽑힌 갯수가 내 길이 중 가장 많이 뽑힌 갯수보다 많으면
            # 얘의 뽑혔던 갯수가 최대가 되고, total 을 갱신해줘야 함 
            if dict[di]>=2 and length_cmp[len(di)] < dict[di] :
                length_cmp[len(di)] = dict[di]
                total[len(di)] = []
                total[len(di)].append(di)
            
            elif dict[di]>=2 : 
                # 내가 새로 갱신될 최댓값은 아니고, 기존 최댓값이랑 똑같으면
                # 나도 total 에 추가 
                if length_cmp[len(di)] == dict[di] :
                    total[len(di)].append(di)

    # print(total)
    # {2: ['AC'], 3: ['CDE'], 4: ['BCFG', 'ACDE']}
    
    for t in total : 
        for tt in (total[t]) :
            answer.append(tt)
                
    answer.sort()
    
    return answer

print(solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2,3,4]))
# print(solution(["ABCDE", "AB", "CD", "ADE", "XYZ", "XYZ", "ACD"], [2,3,5]))
# print(solution(["XYZ", "XWY", "WXA"], 	[2,3,4]	))