[python] programmers - 메뉴 리뉴얼

programmers - 메뉴 리뉴얼

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

프로그래머스

자세한 설명은 위의 링크를 참조하세요.

 

[문제설명]

각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.

 

[문제풀이]

이 문제를 해결하는 과정에서 문제를 잘못이해해서 삽질도 많이하고 시간초과 해결에도 엄청 애를 먹었습니다.

 

처음 생각한 풀이 과정은 다음과 같습니다.

 

1. orders 배열에서 존재하는 알파벳을 모두 합친다.

2. 두번 이상 등장한 알파벳들로만 문자열을 만들고 course 배열의 모든 경우에 대한 조합을 구한다 

3. course 배열의 경우마다 각 조합 별로 카운팅을 해서 max 카운팅된 경우를 정답 배열에 append한다.

 

위 처럼 풀게 되면 아마 13~15번 테스트케이스에서 시간초과가 발생할 것입니다. 그럴수밖에 없는게

orders 배열에 알파벳 26자리가 모두 존재하고, course 배열에 10이 있다면

 5,311,735 가지의 조합의 수에 대해서 계산해야하기때문입니다.

 

따라서 orders 배열의 알파벳을 합쳐서 조합을 한번에 계산하는 것으로는 풀이할 수 없습니다.

 

두번째로 생각한 방법은 다음과 같습니다.

 

1. course 배열을 기준으로 반복문을 열고, orders 배열에 대한 조합을 각각 계산합니다.

2. 그 후 각 course 값의 max 카운팅을 정답 배열에 append 합니다.

 

두번째 방법은 언뜻 생각하면 비효율적이라고 생각할 수 있지만, 조합의 크기가 커지는 경우가 없다는 점에서 

시간초과 문제를 해결할 수 있었습니다.

 

코드는 아래와 같습니다.

from itertools import combinations def solution(orders, course):     answer = []     # 1. 코스메뉴 가지수 별로 조합을 통해 가능한 문자열 뽑기     for co in course:         course_count= {}         for order in orders:             results = list(combinations(sorted(order),co))             for result in results:                 # 2. 각 조합이 order에서 몇번 등장하는지 카운팅하기                   rs = "".join(result)                 course_count[rs] = 0                                  for order in orders:                     flag = 0                     for r in rs:                         if r not in order:                             flag = 1                     if flag == 0:                         course_count[rs] += 1               # 3. max 카운팅을 위해 사전 정렬 후, max와 같은 조합의 경우는 모두 append                 sorted_dic = sorted(course_count.items(), key = lambda x:x[1], reverse = True)         if len(sorted_dic) != 0:             max = sorted_dic[0][1]             for sor in sorted_dic:                 if sor[1] == max and sor[1] >= 2:                     answer.append(sor[0])           return sorted(answer)

개인적으로 제가 작성한 위의 코드는 깔끔하지않다고 생각이 들어서 다른 분의 풀이를 찾아봤습니다.

Counter 모듈을 사용해서 깔끔하게 풀이한 코드가 있어서 참고하고자 가져왔습니다.

출처 : https://subin-0320.tistory.com/77

[Programmers] 메뉴 리뉴얼 (Python)

 

 

from itertools import combinations from collections import Counter def solution(orders, course):     answer = []     for c in course:         temp = []         for order in orders:             combi = combinations(sorted(order), c)             temp += combi         odict = Counter(temp)         if odict:             max_ = max(list(odict.values()))             if max_ >= 2:                 for key, value in odict.items():                     if odict[key] == max_:                         answer.append(''".join(key))                              return sorted(answer)

위처럼 Counter 모듈은 중복 데이터가 있을때 카운팅을 쉽게 지원해주는 모듈입니다. 또한 딕셔너리에서 최대 value를 구하는 방법도 훨씬 깔끔하다고 생각이 듭니다.

 

[알게된 점]

Counter 모듈을 사용하면 중복 데이터를 처리할 때 카운팅을 쉽게할 수 있다.

기본적으로 iterable 객체에 중복 데이터를 처리할 때 Counter를 사용하면 아래처럼 딕셔너리를 반환한다.

>>> Counter(["a", "b", "c", "a", "a", "b"]) Counter({'a': 3, 'b': 2, 'c': 1})

Counter 모듈은 most_common() 이라는 강력한 메소드가 있다.

데이터의 개수가 많은 순으로 정렬된 배열을 리턴해준다.

from collections import Counter Counter('hello world').most_common() [('l', 3), ('o', 2), ('h', 1), ('e', 1), (' ', 1), ('w', 1), ('r', 1), ('d', 1)]

이걸 이용하면 딕셔너리에 최대값을 쉽게 구할 수 있다.

아까 위의 코드를 참고하면

여기서는 딕셔너리의 values를 리스트로 변환해서 max 메소드를 통해 최대값을 구했다.

if c_dic:             res = c_dic.most_common(1)             max_value = res[0][1]             if max_value >= 2:                 for key,value in c_dic.items():                     if c_dic[key] == max_value:                         answer.append("".join(key))

이렇게도 구할 수 있다. !