프로그래머스 / 완전탐색 / 모음사전

문제

---

 

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

프로그래머스

 

입출력

---

 

 

해설

---

 

A, E, I, O, U의 문자만 사용할 수 있으며 길이가 최대 5글자 까지만 등장한다.

 

그러면 최대로 나올 수 있는 문자는 A ~ UUUUU까지이므로 최대 경우의수는 

5 + 5 * 5 + 5 * 5 * 5 ... + 5 * 5 * 5 * 5 * 5가 된다.

 

모두 더해도 3905밖에 되지 않으므로 충분히 모든 경우의 수를 돌면서 찾아도 빠른 시간 내에 찾을 수 있다.

 

그래서 백트래킹을 통해서 해당 문제를 접근해보았다.

 

일단 기본적인 백트래킹을 진행하는데, 여기서 중점은 종료지점일 때 정답인지 판별하는 것이 아니다.

종료지점은 매번 문자가 만들어졌을 때 target과 현재 만들어진 문자가 동일할 때이다.

그렇기 때문에 target과 동일한지를 매번 체크해주었다.

 

그럼 뒤따르는 문제가 종료시점에 answer가 더이상 쌓이지 않아야 문제가 있었다.

그리하여 종료되는 flag라는 변수를 두었고, flag가 true일 때는 더이상 백트래킹을 탐색하지 않기로 했다.

정답코드

---

'''
'25. 10. 1.(수)

1. A,E,I,O,U만 사용할 수 있다.
2. 모두 길이가 5이하의 단어이다.

해당 단어가 몇 번째일지 생각해보아라.
5 * 5 * 5 * 5 * 5
전부 해봤자 3125가지의 경우의 수이다.
backtracking을 통하여서 차례대로 문자를 만들고 해당 문자가 맞는지 확인하면 된다.
'''
answer = 0
flag = False
def backtracking(depth: int, target: str, now: list) -> None:
    global answer, flag
    if flag:return
    if depth == 5:
        return

    if target == ''.join(now):
        flag = True
        return

    for alphabet in 'AEIOU':
        now[depth] = alphabet
        answer += 1
        backtracking(depth + 1, target, now)
        if target == ''.join(now):
            flag = True
            return
        now[depth] = ''
def solution(word):
    global answer
    backtracking(0, word, [''] * 5)
    return answer

 

깃허브 : https://buly.kr/9iGjncY

유튜브 : https://youtu.be/GU0ZonvMQJw