[프로그래머스] 21년 카카오 공채 - 메뉴 리뉴얼

 

문제

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

프로그래머스

 

 

 

시간초과난 풀이를 기억하기 위해 포스팅한다 ㅎ

 

조합을 찾을때, 난 모든 존재할 수 있는 알파벳을 리스트로 구하고 이 리스트에서 조합을 구했는데

알파벳이 총 26개이고, 문제에서 찾는 알파벳 조합의 범위가 1개 ~ 10개까지 이므로

26C1 + ... 26C10은 정말 큰 수일 것이다.

바로 시간 초과..

 

틀린 풀이

answer = []
tempAnswer = []
def solution(orders, course):
    global tempAnswer
    each_alphas = []
    total_alpha_set = set()
    for i in range(len(orders)):
        dic = {}
        for j in range(ord('A'), ord('Z')+1):
            dic[chr(j)] = 0
        for k in orders[i]:
            dic[k] = 1
            total_alpha_set.add(k)
        each_alphas.append(dic)
    total_alpha_set = list(total_alpha_set)
    total_alpha_set.sort()
    
    def check(strs):
        global answer
        realTemp = 0
        for idx, each in enumerate(each_alphas):
            temp = 0
            for alpha in strs:
                temp += each[alpha]
            if temp == len(strs):
                realTemp += 1
                
        if realTemp >= 2:
            return [True, realTemp]
        return [False, 0]
        
    
    def combi(cur, ptr, targetLen):
        global answer
        global tempAnswer
        if len(cur) == targetLen:
            temp = check(cur)
            if temp[0]:
                tempAnswer.append([cur, temp[1]])
            return
        for i in range(ptr, len(total_alpha_set)):
            combi(cur+total_alpha_set[i], i+1, targetLen)
    
    
    for i in course:
        tempAnswer = []
        combi("", 0, i)
        if len(tempAnswer) == 0:
            continue
        tempAnswer.sort(key=lambda x:(-x[1], x[0]))
        k = tempAnswer[0][1]
        for i in tempAnswer:
            if i[1] == k:
                answer.append(i[0])
            else:
                break
    answer.sort()
        
    return answer

 

 

그래서 조금 인터넷을 찾으며 생각해보니, 모든 알파벳 조합에서 조합을 구할 필요가 없이

각각의 사람들이 들고 있는 알파벳 으로만 조합을 구하면

MAX의 연산이 10C1 + ... 10C10이므로, 이전의 계산양보다 훨씬 줄어든다.

통과!

 

통과 풀이

# 1. 존재하는 알파벳 구하고, course 갯수에 맞는 메뉴 조합을 구한다.
answer = []
tempAnswer = []

def solution(orders, course):
    global tempAnswer
    each_alphas = []
    total_alpha_set = set()
    for i in range(len(orders)):
        dic = {}
        for j in range(ord('A'), ord('Z') + 1):
            dic[chr(j)] = 0
        for k in orders[i]:
            dic[k] = 1
            total_alpha_set.add(k)
        each_alphas.append(dic)
    total_alpha_set = list(total_alpha_set)
    total_alpha_set.sort()

    def check(strs):
        global answer
        realTemp = 0
        for idx, each in enumerate(each_alphas):
            temp = 0
            for alpha in strs:
                temp += each[alpha]
            if temp == len(strs):
                realTemp += 1

        if realTemp >= 2:
            return [True, realTemp]
        return [False, 0]

    strSet = set()
    def combi2(cur, ptr, targetLen, order):
        global tempAnswer
        if len(cur) == targetLen and cur not in strSet:
            temp = check(cur)
            strSet.add(cur)
            if temp[0]:
                tempAnswer.append([cur, temp[1]])
            return
        for i in range(ptr, len(order)):
            combi2(cur+order[i], i+1, targetLen, order)

    for target in course:
        tempAnswer = []
        for order in orders:
            order = "".join(sorted(order))
            combi2("", 0, target, order)
        if tempAnswer:
            tempAnswer.sort(key=lambda x:(-x[1], x[0]))
            k = tempAnswer[0][1]
            for i in tempAnswer:
                if i[1] == k:
                    answer.append(i[0])
                else:
                    break

    answer.sort()

    return answer

 

 

 

조합 및 백트래킹의 문제들은 가지치기를 잘 해줘야 할 것 같다