[코딩테스트] 리트코드 - 17. Letter Combinations of a Phone Number

문제

 

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

 

2-9 번호에 해당하는 알파벳이 있다. 인풋으로 2-9를 포함한 문자열이 주어질 때, 각 숫자가 나타낼 수 있는 문자들의 조합을 구하여라!

 

Constraints:

•0 <= digits.length <= 4

•digits[i] is a digit in the range ['2', '9'].

 

예시 1:

Input: digits = "23“

Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

 

설명: 숫자 2는 ['a', 'b', 'c']를, 숫자 3은 ['d', 'e', 'f']를 나타낼 수 있다.

앞의 배열에서 원소 하나, 뒤의 배열에서 원소 하나를 빼서 조합했을 때 가능한 경우는

Output에 나타난 것과 같다.

 

예시 2:

Input: digits = "“

Output: []

 

설명: 빈 문자열이 input으로 들어온 경우 빈 문자열을 output으로 반환

 

예시 3:

Input: digits = "2“

Output: ["a","b","c"]

 

 

풀이

1.

각 숫자가 나타내는 문자열에는 크게 규칙이 없다.

따라서 직접 (숫자 - 문자열) 매핑하는 dictionary를 정의해주자.

 

2.

각 배열을 access하려면, dicitonary의 key로 숫자 하나가 들어가야 한다.

따라서 input으로 들어오는 문자열을 하나 하나 나눠줘야한다.

 

https://stackoverflow.com/questions/113655/is-there-a-function-in-python-to-split-a-word-into-a-list

위와 같이 해주면,

digits = "23" 일때,

digitsList = list(digits) // ["2", "3"]이 된다!

 

3.

각 숫자가 나타내는 문자열은 이제,

dic[숫자] 로 access할 수 있다.

 

그렇다면, 여러 배열이 있을 때,

각 배열에서 한 원소씩 빼내어 만들 수 있는 조합의 경우의 수를 쉽게 구할 수 있는 방법이 있을까?

 

답은 구글 형님을 통해 찾아냈다.

https://stackoverflow.com/questions/19417498/python-choose-one-item-from-every-list-but-make-every-possible-combination

Python: Choose One Item from Every List but Make Every Possible Combination

아주 똑같은 질문을 하신 분이 역시나 있었다!

답은 itertools.product(arg)를 사용하는 것.

 

4. 

itertools.product는

Cartesian Product (카테시안 곱 / 데카르트 곱 / 곱집합.  "각 집합의 원소를 각 성분으로 하는 튜플의 집합")를

구해주는 라이브러리 함수이다.

 

www.geeksforgeeks.org/python-itertools-product/

 

 

위와 같이, itertools.product(원소를 추출하고 싶은 배열들)로 계산하면,

Cartesian product를 반환해주는 것이다.

from itertools import product

arr1 = [1, 2, 3]
arr2 = [5, 6, 7]

list(product(arr1, arr2)) #(1,5), (1,6), (1,7), (2,5), (2,6),(3,5), (3,6), (3,7)

이를 이용해,

문제를 이렇게 풀 수 있겠다.

먼저, 원소를 추출하고 싶은 배열들을 미리 묶어준다.

만약 digits = "23"으로 주어지면,

digitsList는 위에서 봤듯 ["2","3"]이고,

candidates는 [["a","b","c"],  ["d","e","f"]]가 된다.

product 함수에는 *candidates, 따라서 candidates를 풀어서 써준 ["a","b","c"],  ["d","e","f"]가 인수로 전달된다.

 

combos는 이제 [("a", "d"), ("a", "e"), ..]의 형태를 띄게 되고,

이것을  ["ad",  "ae", ..]식으로 반환해야 하기에, map함수를 써준다!

 

 

파이썬 풀이

from itertools import product

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {
            '2': ['a','b','c'],
            '3':['d','e','f'],
            '4':['g','h','i'],
            '5':['j','k','l'],
            '6':['m','n','o'],
            '7':['p','q','r','s'],
            '8':['t','u','v'],
            '9':['w','x','y','z']
        }

        if digits == "":
            return []
        
        digitsList = list(digits)
        candidates = []
        for x in digitsList:
            candidates.append(dic[x])

        combos = list(product(*candidates))
        answer = list(map(lambda x:''.join(x),combos))

        return answer     

예외처리는 따로 해줌.