[Programmers] - 모음사전 (위클리 챌린지) with Python

문제

위클리 챌린지 - 모음사전

 

 

문제 분석하기

길이 5 이하이므로 사전을 전부 만든 후 검색을 해도 속도에 문제가 없어요. 

참고로 사전의 총 길이는

5 + 5^2 + 5^3 + 5^4 + 5^5

 

가 될 거예요 :)

이 사전을 구현하기 위해 재귀 함수를 사용할 수 있겠지만 파이썬의 모듈인 product를 사용하면 보다 손쉽게 구현할 수 있어요.

 

Product 사용하기

Product는 itertools에서 사용할 수 있어요.

itertools에는 Permutation, Combination이 있는데 이것은 순열과 조합이므로 중복을 허락하지 않아요. 이 문제에서는 중복이 필요하기 때문에 Product를 사용해요.

사실 Product는 이름 그대로 product 곱을 위한 모듈이에요.

 

예시를 살펴볼게요!

 

items = [['a', 'b', 'c,'], ['1', '2', '3', '4'], ['!', '@', '#']]

list(product(*items))

# [('a', '1', '!'), ('a', '1', '@'), ('a', '1', '#'), ('a', '2', '!'), ('a', '2', '@'), ('a', '2', '#'), ('a', '3', '!'), ('a', '3', '@'), ('a', '3', '#'), ('a', '4', '!'), ('a', '4', '@'), ('a', '4', '#'), ('b', '1', '!'), ('b', '1', '@'), ('b', '1', '#'), ('b', '2', '!'), ('b', '2', '@'), ('b', '2', '#'), ('b', '3', '!'), ('b', '3', '@'), ('b', '3', '#'), ('b', '4', '!'), ('b', '4', '@'), ('b', '4', '#'), ('c,', '1', '!'), ('c,', '1', '@'), ('c,', '1', '#'), ('c,', '2', '!'), ('c,', '2', '@'), ('c,', '2', '#'), ('c,', '3', '!'), ('c,', '3', '@'), ('c,', '3', '#'), ('c,', '4', '!'), ('c,', '4', '@'), ('c,', '4', '#')]

 

2차원 배열 items가 있을 때 product를 활용하면 각 sub 배열에서 원소를 하나씩 가져와 마치 product 곱처럼 조합을 만들어줘요.

조합인 combination의 경우 주어진 배열 내의 모든 요소를 활용해 조합을 만들지만, product의 경우 개별적인 배열에서의 요소들을 활용해 조합을 만들어요.

여기서 repeat을 사용하면 중복을 허용하는 조합을 만들 수 있어요.

alphabet = ["A", "E", "I", "O", "U"]
from itertools import product

print(product(alphabet, repeat=2)) # 배열과 반복 횟수

 

하지만 기대와 다르게 위의 코드 결과물은 리스트가 아닌 product object가 돼요.

<itertools.product object at 0x102ab1580>

 

product의 결과물을 list로 한 번 감싸면 원하는 결과물이 도출돼요.

print(list(product(alphabet, repeat=2)))

# 결과물은 튜플 배열
# [('A', 'A'), ('A', 'E'), ('A', 'I'), ('A', 'O'), ('A', 'U'), ('E', 'A'), ('E', 'E'), ('E', 'I'), ('E', 'O'), ('E', 'U'), ('I', 'A'), ('I', 'E'), ('I', 'I'), ('I', 'O'), ('I', 'U'), ('O', 'A'), ('O', 'E'), ('O', 'I'), ('O', 'O'), ('O', 'U'), ('U', 'A'), ('U', 'E'), ('U', 'I'), ('U', 'O'), ('U', 'U')]

이것을 활용해서 사전을 완성시키고, 그 사전에서 원하는 단어의 위치를 찾을 수 있어요.

 

최종 코드

def solution(word):
    from itertools import product
    total = []
    alphabet = ["A", "E", "I", "O", "U"]
    for time in range(1, 6):
        total.extend(list(product(alphabet, repeat=time)))
    total.sort()
    return total.index(tuple(word)) + 1

 

문제 풀이 고민

사전을 한 번에 만드는 방법만 생각하다 보니 오히려 문제 풀이에 방해가 되었어요.

가능한 모든 경우의 수를 다 담고, 정렬을 하면 정렬 자체는 O(NlogN) 이므로 시간적으로 충분하기 때문에 조금 더 유연하게 생각할 필요가 있었어요 :)

 

비교적 간단한 문제여서 브레인스토밍 용으로 풀어봤어요!