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

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

틀린 풀이

result_level = []
result = []
max_num = 0


def dfs(cnt, check, idx, count, orders):
    if cnt == count:
        calcul(check, orders)
        return
    for i in range(idx, len(check)):
        if not check[i]:
            check[i] = True
            dfs(cnt + 1, check, i, count, orders)
            check[i] = False


def calcul(check, orders):
    global max_num
    test_str = ""
    count = 0
    for i in range(len(check)):
        if check[i]:
            test_str += chr(65 + i)

    for o in orders:
        flag = True
        for i in test_str:
            if not i in o:
                flag = False

        if flag:
            count += 1

    if count == max_num:
        result_level.append(test_str)
    elif count > max_num:
        max_num = count
        result_level.clear()
        result_level.append(test_str)


def solution(orders, course):
    global max_num

    for i in course:
        check = [False for _ in range(26)]
        max_num = 2
        dfs(0, check, 0, i, orders)
        for i in result_level:
            result.append(i)
        result_level.clear()
    result.sort()
    return result


solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"], [2, 3, 4])

 

해설

dfs()로 A~Z까지 course에 따라 2, 3, 5의 갯수를 뽑는 경우를 다 가져왔다.

그후 orders를 돌면서 해당 단어가 가장 많다면 append를 시키고, 아니면 그냥 넘어가줬다.

이렇게 했을 경우, course의 갯수n만큼 26Cn을 해준 후 orders 연산을 돌게 되는 것이다.

그리고 이렇게 처리할 경우 시간초과가 난다.

 

 

 

 

 

 

정답 풀이

from itertools import combinations
from collections import Counter


def solution(orders, course):
    answer = []

    for num in course:
        array = []
        for order in orders:
            order = sorted(order)
            array.extend(list(combinations(order, num)))
        count = Counter(array)
        print(count)

        if count:
            if max(count.values()) >= 2:
                for key, value in count.items():
                    if value == max(count.values()):
                        answer.append("".join(key))

    return sorted(answer)

solution(["ABCFG", "AC", "CDE", "ACDE", "BCFG", "ACDEH"],	[2,3,4])

 

해설

틀린풀이와 정답 풀이의 큰 차이점은

1. 우선 각 orders의 요소를 뽑아 정렬한다.(아직 이유는 정확히 모르겠다.)

2. list(combinations(order, num))을 통해 order의 단어를 (order)C(num)의 경우를 뽑아준다.

3. 뽑은 요소를 extends로 추가해준다. -> 여기까지 하면 array에는 뭐가 들어있지? orders의 각 요소를 course만큼 뽑아준 경우를 구한 것이구나.

4. Count(array)를 통해 중복된 값들을 전부 count세어준다. Count의 자료구조는 어떻게 구성되어 있는 것일까?

5. if count는 무슨 뜻인가?? 아마 count에 값이 있다면?의 조건문 같은데,, 왜 저렇게 해도 되는걸끼??

또 count.items()는 무슨 의미일까??