[codewars/itertools] 파이썬으로 경우의 수 구하기/여러방법으로 자료형 내 원소의 순열과 조합 구하기/Permutation & Combination with Python with multiple list by itertools : The observed PIN

 

오늘은 파이썬 코드를 이용해 조합을 구하는 문제를 접했습니다.

다같이 레벨업!

Codewars: Achieve mastery through challenge

 

KATA 분석하기

탐정이 된 당신! 당신은 지금 대도둑 Robby the robber의 창고를 발견했습니다. 이 안에는 여태 훔친 모든 물건들이 담겨있고, 우리는 운좋게 Robby the robber가 도어락을 누르는 모습까지 볼 수 있었습니다. 그런데 아불싸, 인공눈물을 넣는 것을 깜빡해서 흐릿한 시야로 본 탐정은 정확한 번호보다는 대강 번호를 누른 자리를 유추하는 수준에서 머무른 겁니다. 무제한으로 누르는 것이 가능하니, 맘놓고 모든 조합을 찾아봅시다.(인접한 번호는 상하좌우로만 고려합니다!)

┌───┬───┬───┐
│ 1 │ 2 │ 3 │
├───┼───┼───┤
│ 4 │ 5 │ 6 │
├───┼───┼───┤
│ 7 │ 8 │ 9 │
└───┼───┼───┘
    │ 0 │
    └───┘

이 문제에서는 아래의 사항들을 고려해야합니다.

• 비밀번호이므로 순서가 고려되어야함, 즉 순열이 고려되어야 합니다!
  • 각 번호마다 인접한 숫자의 리스트를 구해야 합니다.
  • 즉, 여러 리스트에서 순열을 구하는 것!
• 외곽의 있는 숫자들의 인접한 경우의 수는 다르다는 것
• 8과 0의 특이성
• 대각선이 아닌 상하좌우만 고려합니다. 예를들어 5를 눌렀다면 2,4,6,8만 해당됩니다.
• 인자는 문자열로 들어오며, return 값도 문자열로 된 조합의 리스트

 

순열과 조합 내용은 여기를 참조!

 

itertools 로 간단히!

이 모듈은 자체적으로 혹은 조합하여 유용한 빠르고 메모리 효율적인 도구의 핵심 집합을 표준화합니다. 함께 모여, 순수 파이썬에서 간결하고 효율적으로 특수화된 도구를 구성할 수 있도록 하는 《이터레이터 대수(iterator algebra)》를 형성합니다.

itertools에는 파이썬 내에 다양한 조작들을 효율적으로 작업할 수 있는 기능들이 모여있습니다. 예시로, 오늘 우리가 사용할 permutations(), combinations() 뿐만 아니라 평소 종종 쓰는 count()와 repeat도 이에 해당합니다.

 

하나의 리스트 내에서 순열과 조합 구하기: permutations, combinations

순열은 순서를 고려한 경우의 수를 구하면 되고, 조합은 순서가 고려되지 않은 경우의 수를 의미한다. 예시로, 1과 2를 이용해 순열과 조합을 만든다면, 순열은 (1, 1), (1, 2), (2, 1), (2, 2)로 총 4개를 구하면 되고, 조합의 경우에는 1이나 2가 뽑히는 타이밍을 고려하지 않기 때문에 (1, 1), (1, 2), (2, 2) 로 총 3개를 구하면 되는 것이다. itertools를 이용해 간단하게 하나의 자료형 내에서 조합을 찾는 방식을 확인해보자.

from itertools import permutations, combinations
#순열
#iter를 반환하기에 list화 해준다.
>>> list(permutations('ABCD', 2))
... [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'A'), ('B', 'C'), ('B', 'D'), ('C', 'A'), ('C', 'B'), ('C', 'D'), ('D', 'A'), ('D', 'B'), ('D', 'C')]

#조합
#iter를 반환하기에 list화 해준다.
>>> list(combinations('ABCD', 2))
... [('A', 'B'), ('A', 'C'), ('A', 'D'), ('B', 'C'), ('B', 'D'), ('C', 'D')]

permutations와 combinations는 iter를 반환하므로, 결과물을 확인하기 위해서는 list()를 입혀주자!

 

 

그러나 이것은 맛보기,

우리는 여러개의 리스트에서 구해야합니다.

레고!

여러개 리스트에서 구하기: product

그림판으로 그렸다.

하지만 문제에서는 여러개의 리스트에서 해야한다는 것입니다. 이럴 땐, product를 이용합니다. product는 데카르트 곱(cartesian product), 중첩된 for 루프와 동등합니다. 데카르트 곱은 여러 집합의 원소들로 구성된 모든 경우의 순서쌍이라고 생각하면 될 것 같습니다.

from itertools import product


adjacent = [["a", "b", "c"],["a", "b"], ["d", "e", "f"]]

list(product(*list(adjacent)))

[('a', 'a', 'd'), ('a', 'a', 'e'), ('a', 'a', 'f'), ('a', 'b', 'd'), ('a', 'b', 'e'), ('a', 'b', 'f'), ('b', 'a', 'd'), ('b', 'a', 'e'), ('b', 'a', 'f'), ('b', 'b', 'd'), ('b', 'b', 'e'), ('b', 'b', 'f'), ('c', 'a', 'd'), ('c', 'a', 'e'), ('c', 'a', 'f'), ('c', 'b', 'd'), ('c', 'b', 'e'), ('c', 'b', 'f')]

 

 

나의 풀이

나는 가장 간단해보이는 방법인 product를 사용했다. 전체 코드는 아래와 같다. 자세한 내용은 주석을 참고해주세요~!

from itertools import product
from collections import defaultdict


def get_pins(observed):
    adjacent, observed_li = list(), list(observed)
    
    # 숫자 다이얼의 레이아웃을 고려
    upper_num = lambda x: x-3 if x not in [1, 2, 3] else ""
    under_num = lambda x: x+3 if x not in [7, 8, 9] else (0 if x==8 else "")
    left_num = lambda x: x-1 if x not in [1, 4, 7] else ""
    right_num = lambda x: x+1 if x not in [3, 6, 9] else ""

    # 입력받은 숫자별로 인접한 숫자를 구한다.
    for i in observed_li:
        adj_el = list()
        if i == "0":
            adj_el = ["8", "0"]
        else:
            x = int(i)
            adj_el += map(str, [
                upper_num(x), under_num(x), left_num(x), right_num(x), i
            ])
            
        # "" 하나만 있는 경우 에러를 출력할 수 있으므로 삭제.
        while "" in adj_el:
            adj_el.remove("")
        adjacent.append(adj_el)
    
    # 경우의 수를 구한다.
    a = list(
        product(*list(adjacent))
    )

    return ["".join(a_l) for a_l in a]

 

고수의 풀이

ㅋㅋ 이렇게 짧게 쓰다니...굳이 다이얼 고려하는 람다를 짤 필요가 없었다 ㅠ 역시 모르는 것이 생기면 전신이 고생한다😥

오늘의 교훈: 직접 입력하는 것이 나을 때에는 직접 그냥 입력하자~ 괜히 함수 만들어서 연산 늘리지 말고

from itertools import product

ADJACENTS = ('08', '124', '2135', '326', '4157', '52468', '6359', '748', '85790', '968')

def get_pins(observed):
    return [''.join(p) for p in product(*(ADJACENTS[int(d)] for d in observed))]

 

 

참고자료

 

itertools — 효율적인 루핑을 위한 이터레이터를 만드는 함수 — Python 3.10.0 문서

 

Remove an item from a list in Python (clear, pop, remove, del) | note.nkmk.me

 

All possible permutations of a set of lists in Python

[해석학] 데카르트 곱이란?