프로그래머스 | Python | 완전탐색 | 모음사전 (Lv.2)

https://school.programmers.co.kr/learn/courses/30/lessons/84512

프로그래머스

 

문제 분석

이 문제는 특정 단어 word가 사전 순서로 몇 번째인지를 계산하는 문제입니다.

모든 단어는 길이 5 이하이고, 알파벳 모음 ['A', 'E', 'I', 'O', 'U']만을 사용합니다.

사전은 사전 순서대로 정렬된 순열로 구성됩니다.

 

예를 들어:

• 길이 1: "A", "E", "I", "O", "U"
• 길이 2: "AA", "AE", "AI", ..., "UU"
• 길이 3: "AAA", "AAE", ..., "UUU"

---

접근 방식 (완전 탐색)

1. 모든 단어를 생성:
   •   길이 1부터 5까지 가능한 모든 조합을 생성.
   •   이를 사전 순서대로 나열.
2. 단어의 위치를 계산:
   •   생성된 단어 리스트에서 word의 인덱스를 찾고, 1-based index로 변환.

---

코드 구현

from itertools import product

def solution(word):
    # 알파벳 모음 리스트
    vowels = ['A', 'E', 'I', 'O', 'U']

    # 모든 단어를 사전 순서로 생성
    dictionary = []
    for length in range(1, 6):  # 단어 길이는 1부터 5까지
        for combination in product(vowels, repeat=length):
            dictionary.append(''.join(combination))

    # 사전 순서로 정렬
    dictionary.sort()

    # word가 몇 번째인지 반환 (1-based index)
    return dictionary.index(word) + 1

---

코드 설명

1. itertools.product를 사용한 모든 조합 생성

•   product(vowels, repeat=length):
  •   vowels에서 길이가 length인 모든 조합을 생성.
  •   예: length=2일 때, ('A', 'A'), ('A', 'E'), ....
• '  '.join(combination):
  •   튜플 형태의 조합을 문자열로 변환.
  •   예: ('A', 'E') → "AE".

2. 사전 리스트 생성

•   모든 길이(1~5)에 대해 가능한 단어를 생성하고 리스트에 추가.
•   생성된 단어 리스트는 이미 사전 순서로 정렬됩니다.
  itertools.product(vowels, repeat=length)는 사전 순서대로 조합을 생성합니다.
  
  즉, "A" → "E" → "I" → "O" → "U" 순으로 증가하며 조합이 만들어지므로,
  길이가 작은 단어부터 자동으로 사전 순서로 정렬된 상태가 됩니다.
  
  따라서 dictionary.sort()를 따로 하지 않아도 이미 정렬된 상태입니다.

3. 단어 위치 찾기

•   dictionary.index(word):
  •   word가 사전 리스트에서 몇 번째에 있는지 0-based 인덱스를 반환.
•   +1:
  •   문제 요구사항에 맞게 1-based index로 변환.