[프로그래머스] 메뉴 리뉴얼 [Level 2] (python 파이썬)

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

프로그래머스

 

 

 

 

 

 

 

 

from itertools import combinations
def solution(orders, course):
    ans = []
    for i in course:
        d = {}
        for order in orders:
            for com in list(combinations(order, i)):
                d["".join(sorted(com))] = 0
        for j in d:
            for order in orders:       
                c = 0
                for alp in j:
                    if alp not in order:
                        c = 1
                        break
                if c == 0:
                    d[j] +=1
        pgm =sorted(d.items(), key = lambda item: item[1])
        if pgm != []:
            max = pgm[-1][1]
            if max >1:
                while 1:
                    now = pgm.pop()
                    if now[1] != max:
                        break
                    else:
                        ans.append("".join(now[0]))
    return sorted(ans)

 

 

 

 

이 문제는 모든 경우의 수를 구해 하나하나 다 확인해보는 부르트포스 알고리즘이다. 

 

 

나는 이 문제의 가장 어려운 점은 부르트 포스가 아닌 다른 방법이 있지 않을까 하는 생각에 시간을 많이 낭비하게 하는 것이라 생각한다.

 

 

order 배열이 20 이하, order의 원소의 크기는 10 이하, course 의 크기는 10 이하에, 원소의 종류도 알파벳 대문자이며, 중복되지 않는다는 점에 가능한 경우의 수가 다른 문제에 비해 월등히 작다. 

 

 

따라서 모든 경우를 들여다 보는 경우도 고려해봐야 한다.

 

 

 

또한 개인적으로 모든 경우를 다 보는 것 외에 다른 방법이 생각나지 않았다. ㅎㅎㅎ

 

 

 

 

 

 

따라서 

 

1.  딕셔너리 생성 (중복을 피하기 위해)

 

 

 

 

 

2. course 를 돌면서

 

       2-1  그 안에서 order 를 돈다. (course가 1일 때, 2일 때 .....)

 

               2-2 이 때, order 에서 course 길이의 모든 조합의 수를 딕셔너리에 정렬해서 넣는다 ( 나중에 확인하면 정렬이 안되는 입력값이 있기 때문에 정렬). (order C couse 경우의 수)

 

      2-3 order을 나오면 딕셔너리에는 course 길이의 모든 조합의 수가 있을 것이다.

 

               2-4 그 조합의 수를 돌면서.

 

                          2-5  그 안에서 다시 order을 돈다. (각각의 경우에 대해)

 

                                     2-6 각각의 order에 대해 그 조합이 있으면 조합의 개수에 +1 한다. (딕셔너리이므로 시간 절약 가능).

 

      2-7 조합의 수를 모두 돌면 딕셔너리에는 현재 course 길이의 모든 조합의 수가 키로 그 조합의 수가 들어간 횟수가 값으로 들어갈 것이다.  

 

      2-8 이 딕셔너리를 값에 대해 정렬 하면 가장 많이 주문한 조합 순으로 정렬 될 것이다.

     

 

2-9 여기에서 최대의 조합만을 ans에 append한다. (중복인 경우 다 append).

 

     

2-10 이 과정을 다하면 딕셔너리는 초기화, 다음 course 길의 조합의 수를 담는 딕셔너리가 된다.  (즉 각각의 course에 대해서만 입력되는 딕셔너리).

     

 

 

 

 

3. course를 다 돌게 되면 ans에는 정답의 경우의 수가 입력될것이다. 

 

 

 

 

 

4. 이를 정렬에서 리턴!!

 

 

 

 

 

 

다른 문제를 풀 때에도 가능한 경우의 수가 작은 경우 모든 경우를 다 들여다 보는 방법을 생각해낼 수 있어야 할 것이다.