[pgs카카오 메뉴리뉴얼] Counter, Combinations

프로그래머스 메뉴 리뉴얼, 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 활용했을 때의 시간 결과

github