프로그래머스 메뉴 리뉴얼, 2021 카카오 블라인드 테스트
itertools.Combinations
itertools의 combinations와 permutations는 말 그대로 가능한 경우들을 빠르게 계산해주는 메소드이다.
아래 이미지처럼 'ABCD'에서 3개의 문자(character)를 뽑을 때 permutation과 combination을 사용하면 모든 조합을 쉽게 얻을 수 있다. len()을 찍어보면 4P3, 4C3 값들과 일치한다.
작업 속도가 그다지 빠르지 않기 때문에 다른 방법이 있다면 사용하지 않는 편이 낫지만, 이 문제에서는 이렇게 조합을 뽑아내는 것 말고 다른 방법이 떠오르지 않았고, 코드에 포함을 하고도 전체 테스트케이스를 무사히 통과할 수 있었다.
collections.Counter
Counter 또한 직관적인 이름을 가지고 있다. 데이터 구조 안에 있는 element들의 개수를 세어준다.
아래처럼 corpus 안의 모든 단어들을 한 바퀴 돌면서 vocab dictionary를 만들어줄 수도 있는데, 이 작업을 좀 더 간단한 코드로 실행할 수 있게 해준다.
for word in corpus:
if word not in vocab:
vocab[word] = 1
else:
vocab[word] += 1뒤에 .most_common()을 붙여 가볍게 빈도 내림차순 정렬까지 가능하다. 다만 내장함수임에도 불구하고 몇번의 실험 결과 직접 세는 방식(O(n)) 보다 시간이 더 걸린다. 이 문제에서도 두 가지를 테스트 해보았고 결과는 동일했다. 코드가 조금 더 지저분하지만 테스트에서는 직접 세는 쪽을 자주 활용할 것!
Counter(corpus).most_common()Question
[문제]
각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요.
Solution
기본적으로 주어진 메뉴 구성 숫자로 combination을 뽑아내서 count를 하고, 상위에 있는 메뉴들을 추려내는 방식을 사용한다. Count를 할 때 O(n)으로 직접 세는 방식과 collections.Counter를 사용하는 방식 두 가지를 테스트해보았다. 이 테스트는 항상 직접 세는 방식이 더 빠르게 실행되는 것으로 보인다.
PSEUDO
- orders의 각 인자들을 오름차순 정렬 ('abcde'와 'bea'에서 모두 'ab' 조합이 존재해야 하므로, 이걸 해주지 않으면 combinations를 사용했을 때 'ab'와 'ba'가 각각 포함된다)
- course의 메뉴 개수마다 combinations(orders, n개)를 실행시켜서 조합을 뽑아내고, 메뉴 개수별 counter data를 만들어낼 것 (2개 메뉴를 살펴본다면, 모든 orders에서 각각 combinations( ,2)를 해주고 각 조합들의 개수를 세어 줌)
- 메뉴 개수별 counter 데이터를 sorting 해준 후 가장 빈도가 높은 조합(들)을 answer에 append
Sol 1. 직접 count
def sol(orders, course):
orders = list(map(sorted, orders))
combi_dict = defaultdict(lambda: dict())
for nums in course:
for o in orders:
combis = list(map(lambda x: ''.join(x), combinations(o, nums)))
for c in combis:
if c not in combi_dict[nums]: combi_dict[nums][c] = 1
else: combi_dict[nums][c] += 1
ans = list()
for num in combi_dict:
sort = sorted(combi_dict[num].items(), key=lambda x: x[1], reverse=True)
max_cnt = sort[0][-1]
if max_cnt == 1:
continue
for menu, cnt in sort:
if cnt == max_cnt: ans.append(menu)
else: break
return sorted(ans)Sol 2. Counter 메소드 사용하기
counter를 만들 때 직접 개수를 세지 않고 list에 모두 append 해뒀다가 Counter 메소드 활용
def sol_counter(orders, course):
orders = list(map(sorted, orders))
combi_dict = defaultdict(lambda: list())
for nums in course:
temp = list()
for o in orders:
combis = list(map(lambda x: ''.join(x), combinations(o, nums)))
temp += combis
combi_dict[nums] = Counter(temp).most_common()
ans = list()
for num in combi_dict:
if combi_dict[num]:
max_cnt = combi_dict[num][0][-1]
if max_cnt == 1:
continue
for menu, cnt in combi_dict[num]:
if cnt == max_cnt: ans.append(menu)
else: break
return sorted(ans)Counter 메소드보다 직접 세는 게 빠름. 각 케이스별로 위쪽이 직접, 아래쪽이 Counter 활용했을 때의 시간 결과
