[Algo] 전화번호 문자 조합 : LeetCode-17
내 주 언어인 Python파이썬으로 틈틈이 Algorithm알고리즘 문제풀이를 하던 도중 itertools 패키지의 product 함수의 기능을 알게 되었다.
특히, 원소들 간 중복순열을 구현할 때 DFS로 복잡하게 구현할 필요 없이 간단하게 사용할 수 있는 툴이다.
물론 자매품으로 itertools.permutations()와 itertools.combinations()가 있다.
이들 역시 중복을 허용하지 않는 순열과 조합을 간단하게 구현할 때 쓰일 수 있다.
LeetCode-17 Letter Combinations of a Phone Number
이 문제는 2에서 9 사이의 숫자 sequence가 주어졌을 때 다음 그림과 같이 각 숫자에 해당되는 문자 매핑을 이용하여 가능한 문자 조합들을 찾는 것이다. 아래 그림은 문제에서 주어진 그림이다.
Figure. 1 전화번호 숫자-문자 매핑
[1] itertools.product()를 이용한 풀이
from itertools import product
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
# 1. for input ''
if not digits:
return []
# 2. num-chars mapping
letters = {'2': 'abc', '3': 'def',
'4': 'ghi', '5': 'jkl', '6': 'mno',
'7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
# 3. list of characters for each digit
maps = [letters[n] for n in digits]
# 4. Find permutations with repetition
return [''.join(i) for i in product(*maps)]
'''
example)
digits = "23"
maps = ["abc", "def"]
output = ["ad","ae","af","bd","be","bf","cd","ce","cf"]
'''
코드는 다음과 같이 매우 간단하게 짤 수 있다.
digits의 길이가 0인 경우에 대해 전처리를 해준다.- 각 숫자-문자 조합을
dictionary로 매핑해준다. - 이 매핑을 입력 digits에 맞게 미리 list로 만들어 논다.
- 중복순열을 구하여 문자 조합 경우의 수를 찾아 return 한다.
1-1. itertools.product(*iterables, reapeat=1)
-
itertools.product()함수는 다수의 iterable들을 입력 인자로 받아 이 iterable들의 Cartesian product내적를 구하는 함수이다. -
위의 예시처럼
itertools.product('abc', 'def')는strtype의 iterable'abc'와'def'를 인자로 받아 중복순열을 생성하면, 다음과 같은 조합이 나온다.
["ad","ae","af","bd","be","bf","cd","ce","cf"]
1-2. 왜 product의 인자로 *maps를 써주었을까?
itertools.product()의 입력 인자로 들어가는 iterable들의 개수는 항상 2개로 고정되어 있진 않을 것이다. 실제 위 문제의 digits의 길이는 0 에서 4 사이라고 주어져 있어, 가변길이의 인자를 함수 입력으로 넣어주어야 한다.
우선, Python 함수는 기본적으로 Call by object-reference로, 객체에 대한 reference를 인자로 넘겨준다는 점을 알고 있어야 한다.
만약 위의 예시에서 *maps 대신 그냥 maps를 써준다면, 즉 [''.join(i) for i in product(maps)]일 때에는, maps의 reference만 받아오기 때문에 원소를 ‘하나씩만’ 불러와 product연산을 진행한다. 다시 말하면, ('abc', ), ('def', )에 대한 product 연산을 하여 원하는 결과를 얻지 못하게 될 것이다.
따라서, 우리는 itertools.product() 함수에 ‘다수의’ str type iterable들을 parameter로 넘겨주어 중복순열을 구하고자 하기 때문에, str type iterable들이 담긴 list인 maps를 ‘참조’하여(*maps) 원소들 자체의 reference들을 함수에 전달해주어야 한다.
[''.join(i) for i in product(*maps)]
1-3. itertools.product() tips
또 주의할 점으로는, 이 함수는 일종의 generator제너레이터 이기 때문에 필요할 때만 결과 값을 생성하기 때문에, 실제 다 생성하여 저장하고 싶다면 list로 묶어주면 되겠다.
번외로 같은 iterable들에 대해 중복순열을 구하는 방법을 알아보면, 뒤의 repeat=n 인자를 조정해주면 된다. 예를 들어, 위 문제에서 digits = '222'가 입력으로 들어왔다고 하면, itertools.product('abc',repeat=3)으로 구현하면 다음과 같은 결과가 나올 것이다.
[('a', 'a', 'a'),
('a', 'a', 'b'),
('a', 'a', 'c'),
('a', 'b', 'a'),
('a', 'b', 'b'),
('a', 'b', 'c'),
('a', 'c', 'a'),
('a', 'c', 'b'),
('a', 'c', 'c'),
('b', 'a', 'a'),
('b', 'a', 'b'),
('b', 'a', 'c'),
('b', 'b', 'a'),
('b', 'b', 'b'),
('b', 'b', 'c'),
('b', 'c', 'a'),
('b', 'c', 'b'),
('b', 'c', 'c'),
('c', 'a', 'a'),
('c', 'a', 'b'),
('c', 'a', 'c'),
('c', 'b', 'a'),
('c', 'b', 'b'),
('c', 'b', 'c'),
('c', 'c', 'a'),
('c', 'c', 'b'),
('c', 'c', 'c')]
[2] DFS를 이용한 풀이
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
if not digits:
return []
len_digits = len(digits)
maps = {'2': 'abc', '3': 'def',
'4': 'ghi', '5': 'jkl', '6': 'mno',
'7': 'pqrs', '8': 'tuv', '9': 'wxyz'}
# 1. DFS implementation
def dfs(idx, string):
# End-statement : string 길이가 digits 크기 만큼 차면 result에 해당 조합 추가 후 back-tracking
if len(string) == len_digits:
result.append(string)
return
for i in range(idx, len_digits):
# idx : {idx+1}번 째 iterable에서의 경우
for j in maps[digits[i]]:
dfs(i+1, string+j)
# 2. DFS 시작
result = []
dfs(0, "")
return result
Leave a comment