문제
https://school.programmers.co.kr/learn/courses/30/lessons/84512
프로그래머스
SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프
programmers.co.kr
입출력

해설
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
'코딩테스트 > programmers' 카테고리의 다른 글
| 프로그래머스 / 구현, 정수론 / k진수에서 소수 개수 구하기 (0) | 2025.10.11 |
|---|---|
| 프로그래머스 / 스택 / 뒤에 있는 큰 수 (0) | 2025.10.05 |
| 프로그래머스 / 집합 / [1차] 뉴스 클러스터링 (0) | 2025.10.01 |
| 프로그래머스 / 백트래킹 / 타겟 넘버 (0) | 2025.09.24 |
| 프로그래머스 / bfs / 게임 맵 최단거리 (0) | 2025.09.23 |