2021 KAKAO BLIND RECRUITMENT 메뉴 리뉴얼 (lv2)

정답 코드

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)
            #조합 함수. 순서 없이(중복 없이) 리스트에서 C개 요소를 선택하여 리스트로 리턴
            temp += combi
        counter = Counter(temp) #Counter() : 문자열이나, list 의 요소를 카운팅하여 많은 것부터 딕셔너리형태로 리턴한다 ex) {'s':2}
        if len(counter) != 0 and max(counter.values()) != 1:
            answer += [''.join(i) for i in counter if counter[i] == max(counter.values())]

    return sorted(answer)

---

배운 점

• Python의 itertools를 이용하면 순열과 조합을 for문 없이 구현할 수 있다.

순열

permutation

순열이란 몇 개를 골라 순서를 고려해 나열한 경우의 수를 말한다. 즉, 서로 다른 n 개 중 r 개를 골라 순서를 정해 나열하는 가짓수이며 순열이라는 의미의 영어 ‘Permutation’의 첫 글자 P를 따서 nPr로 표시한다.

순열은 순서를 고려하기 때문에 [A, B, C]의 리스트에서 2개의 원소를 골라 순서를 정해 나열하면
[(A, B), (A, C), (B, A), (B, C), (C, A), (C, B)] 가 나오게 된다. 즉 순열에서는 (A, B)와 (B, A)는 다른 것이다.

import itertools

arr = ['A', 'B', 'C']
nPr = itertools.permutations(arr, 2)
print(list(nPr))

결과 : [('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]

조합

combination

조합이란 서로 다른 n개 중에서 r개(n≥r) 취하여 조를 만들 때, 이 하나하나의 조를 n개 중에서 r개 취한 조합이라고 한다.

조합은 순서를 고려하지 않기 때문에 [A, B, C]의 리스트에서 2개의 원소를 골라 나열하면
[(A, B), (A, C), (B, C)] 가 나오게 된다. 조합은 (A, B)와 (B, A)는 같은 것으로 취급한다.

import itertools

arr = ['A', 'B', 'C']
nCr = itertools.combinations(arr, 2)
print(list(nCr))

결과 : [('A', 'B'), ('A', 'C'), ('B', 'C')]

이외에 유용한 함수

zip()

동일한 개수로 이루어진 iterable한 객체들을 인수로 받아 묶어서 iterator로 반환

    z = zip([1, 2, 3], ('A', 'B', 'C'))
    print(next(z)) # (1, 'A')
    print(next(z)) # (2, 'B')
    print(next(z)) # (3, 'C')

all()

iterable한 객체를 인수로 받아서 원소가 모두 참이면 True, 아니면 False를 반환

    a = all([1, 2, 3]) # True
    a = all([0, 1, 2]) # False

any()

iterable한 객체를 인수로 받아서 원소가 하나라도 참이면 True, 아니면 False를 반환

    a = any([0, 1, 2]) # True
    a = any([0, False, []] # False

chain()

iterable한 객체들을 인수로 받아 하나의 iterator로 반환

    c1 = [1, 2]
    ca = ['A', 'B']
    c = itertools.chain(c1, ca)
    print(next(c)) # 1
    print(next(c)) # 2
    print(next(c)) # A
    print(next(c)) # B]

조합을 구현해야하는 알고리즘 문제를 풀면서 for문을 중첩해서 풀기 보다 다른 방법이 없을까 싶어서 찾던 중 itertools를 활용하여 간단하게 구현하는 것을 알게되었다.