UUUUUUUU 매그내릭!
마지막 단어가 "UUUUU"라는걸 보자마자 말왕의 매그내릭이 떠올라버렸....다
백준 2805번 문제 풀이
문제
사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는, 길이 5 이하의 모든 단어가 수록되어 있습니다. 사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며, 마지막 단어는 "UUUUU"입니다.
단어 하나 word가 매개변수로 주어질 때, 이 단어가 사전에서 몇 번째 단어인지 return 하도록 solution 함수를 완성해주세요.
[제한사항]
word의 길이는 1 이상 5 이하입니다.
word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.
[입출력 예]
| word | result |
|---|---|
"AAAAE" | 6 |
"AAAE" | 10 |
"I" | 1563 |
"EIO" | 1189 |
문제 해석하기
중복순열
이진 탐색은 정렬된 데이터에서 특정 값을 효율적으로 찾기 위해 사용하는 알고리즘
매 반복마다 검색 범위를 절반으로 줄여가며 최적의 해를 탐색한다
*나무 자르기 문제의 경우도 검색 범위가 커질 수 있기 때문에 효율적인 탐색을 위해 사용함
- 일단, 모음을 배열 안에 넣어준다.
- 모음을 배열안에 넣어주어, 해당 모음을 바탕으로 만들어질 수 있는 모든 조합을 만들어보려고 함
- 중복 순열을 이용하여, 가능한 모든 조합을 생성해준다.
- 중복 순열을 만들기 위해서
from itertools import product를 import - for문을 이용해서 주어진 모음들을 바탕으로 튜플을 만들어줌
- itertools는 튜플로 요소를 반환하기 때문에 이 요소를 join을 통해 단어로 만들어준다
- 중복 순열을 만들기 위해서
- word를 바탕으로 몇번째 단어인지 알기 위해서 index를 찾아준다
- index가 0부터 시작이기 때문에 +1을 해주어 해당하는 단어의 위치를 찾아줌
문제 해석 중 생각해볼 점
1) sort() 잊지 말기
우리가 찾고자하는 words는 'A,E,I,O,U' 순서로 정렬되어 있기 때문에 index로 값을 찾으려면 해당 내용을 정렬을 해주어야 한다. 그런데 sort를 잊어서 해당 내용을 추가한 후에 코드를 다시 작성해주었다.
2) 중복 순열 대신 사용할 수 있는 다른 방식이 있지 않을까?
우리가 탐색해야하는 수가 많아지는 경우에는 시간초과나 런타임에러가 생길 수도 있을 것 같다는 생각이 들었다. 중복 순열을 사용하는 방식 대신에 다른 알고리즘이 무엇이 있을 까 생각해보았다.
=> DFS를 사용하는 방식도 의미가 있을 것 같아서 아래에서 해당 내용에 대한 코드를 작성해보았다.
from itertools import product
def solution(word):
vowels = ['A','E','I','O','U']
dict = []
answer = 0
for i in range(5):
for j in product(vowels,repeat = i+1):
dict.append(''.join(j))
dict.sort()
return dict.index(word)+1DFS를 사용하는 방식 - 깊이우선탐색
def solution(word):
dictionary = []
vowels = 'AEIOU'
def dfs(cnt, w):
# 기저 조건: 단어의 길이가 5가 되면 더 이상 탐색하지 않는다
if cnt == 5:
return
for i in range(len(vowels)):
# 현재 단어에 모음을 추가하고 리스트에 추가
dictionary.append(w + vowels[i])
# 재귀 호출로 다음 단계 탐색
dfs(cnt + 1, w + vowels[i])
# 빈 문자열부터 시작해 DFS 탐색
dfs(0, '')
# 주어진 단어의 인덱스를 찾아 반환 (1-based index)
return dictionary.index(word) + 1DFS를 사용한 이유
- 모든 가능한 조합을 탐색하는 데 유용하다.
- DFS는 재귀적으로 탐색하며 현재 위치에서 가능한 모든 경로를 탐색한다.
- 따라서, 한단계 더 깊이 탐색하면서 새로운 문자를 추가하고 조합할 수 있도록 한다.
- 재귀 구조가 간단하다
- cnt == 5 라는 조건을 설정하여, 탐색하고자 하는 길이를 조정할 수 있다.
- 모든 조합을 순서대로 탐색이 가능하다
- 조합을 굳이 sort를 해주지 않아도 사전에 있는 방식 그대로 순서대로 추가되기 때문에 정렬을 해줄 이유가 사라진다.
오늘의 회고
중복 순열을 사용하는 방식에 대해서 알게 된것과 더불어, dfs를 사용해서 새롭게 코드를 작성해보면서 코드 작성 방식에 대해 조금 더 넓은 시각을 갖게 된 것 같다.
