코딩 테스트/문제풀이 Python ver.
[문제풀이 py] P84512 모음사전
Gaejirang-e
2023. 7. 6. 03:36

모음사전 / DFS ⚓
🎠. for in 반복문에서 '문자열'도 문자 하나씩 빼올 수 있다.
🎠. python '슬라이싱(slicing)' 방법을 알아야 한다.
🎠. dfs 알고리즘을 구현할 줄 알아야 한다 => '종료조건 + 재귀적 확장'
🎠. '지역 네임스페이스' 내에서 '전역변수의 값의 할당'하는 방법을 알아야 한다 => 'global'

vowels = 'AEIOU'
cnt = 0
g_word = ""
res = 0
def dfs(s):
global cnt, res
if s == g_word:
# print("res:", cnt)
res = cnt
return
cnt += 1
# print(s)
# 종료조건
if len(s) == 5:
return
# 재귀적 확장
for vowel in vowels:
dfs(s+vowel)
s[:-1]
def solution(word):
global g_word
g_word = word
dfs("")
return res
💡. 문제 접근 방법
: 조건을 만족(길이 5)할 때까지 똑같은 동작(?)을 반복하고,
조건을 만족(길이 5)하면, 전과 다른 문자로 조건을 만족시키는 방식을 보며 DFS를 생각했다
즉, 길이를 늘려나가는 과정에서 루트에서 시작해 리프노드까지 최대한 내려가는 DFS가 생각났다.
🤡. 실수한 부분
: 지역 네임스페이스에서 전역변수의 값을 수정할 때 이 변수가 전역변수임을 알려야 하는 것을 몰랐다.