[Python 알고리즘] 프로그래머스 모음사전 풀이

 

프로그래머스 완전탐색 문제인

[모음사전]을 파이썬으로 풀어보겠습니다!

 

고득점 키트의 완전탐색 유형에 있는 문제입니다.

Lv2로 난이도 하에 해당하기 때문에

접근방법만 떠올리면 어렵지 않게 풀 수 있습니다.

 

프로그래머스

 

문제 설명

사전에 알파벳 모음 'A', 'E', 'I', 'O', 'U'만을 사용하여 만들 수 있는

길이 5 이하의 모든 단어가 수록되어 있습니다.

사전에서 첫 번째 단어는 "A"이고, 그다음은 "AA"이며

마지막 단어는 "UUUUU"입니다.

단어 하나 word가 매개변수로 주어질 때

이 단어가 사전에서 몇 번째 단어인지 return 하도록

solution 함수를 완성해주세요.

 

제한사항

1. word의 길이는 1 이상 5 이하입니다.

2. word는 알파벳 대문자 'A', 'E', 'I', 'O', 'U'로만 이루어져 있습니다.

 

 

 

이 문제 전형적인 백트래킹 문제입니다.

이거 깊이 우선 탐색이라 DFS 아니야? 라는 생각이 들지만

사실 백트래킹을 포함한 형태의 DFS라고 하는게 정확합니다.

 

그렇다면 접근방법부터 떠올려보시죠

문제에서 주어진대로 일단 쭉 나열해봅시다.

 

A

AA

AAA

AAAA

AAAAA

AAAAE

AAAAI

AAAAO

AAAAU

AAAE

AAAEA

AAAEE

AAAEI

AAAEO

AAAEU

AAA

 

나열해보니 어떤 규칙성이 보이지 않나요?

저희는 총 다섯자리를 채울거에요.

A부터 가능한 전부 채워봅시다.

 

모든 자리의 수를 체크해야 되기 때문에

문자를 추가할 때마다 생성된 문자열을 전부 기록합니다.

가장 우선순위가 높은 A부터 쭉 채우다 보니 5자리를 꽉 채우게 되었네요!

이제부터는 다음 우선순위인 문자도 고려해볼까요?

가장 마지막 자리에 다음 우선순위인 E,I,O,U 를 차례대로 채워줍니다.

 

이제 더이상 채울 수 있는 경우가 없으니

자리수를 한칸 앞으로 당겨봅시다.

한자리수 앞으로 당겨 E를 추가해주니 가능한 경우의 수가 많이 생겼네요!

새로운 문자열 (AAAE)에 또다시 다섯개의 문자(A,E,I,O,U)를 채워봅시다.

동일한 방식으로 I,O,U 도 채워주면 벌써 많은 문자열이 생성됐어요.

이런식으로 쭉쭉 경우의 수를 고려하다보면

제가 원하는 문자열에서 Stop 해주면 되겠죠

 

이제 코드를 살펴볼까요?

def solution(word):
    
    alpha_list = ["A","E","I","O","U"]
    cnt = 0
    
    def backtracking(ans):
        nonlocal cnt
        cnt += 1
        
        # 내가 원하는 단어에 도달하면 재귀를 멈추고 cnt 리턴하기
        if "".join(ans) == word:
            return True
        
        # 5자리까지 채웠다면 한단계 전으로 돌아가기 -> ans.pop()
        if len(ans) == 5:
            return False
        
        for alpha in alpha_list:
            ans.append(alpha)
            if backtracking(ans):
                return True
            ans.pop()
        
        
    for s in alpha_list:
        if backtracking([s]):
            return cnt
        
    return 0

 

전형적인 백트래킹 템플릿입니다.

이 문제는 접근방법만 잘 파악했다면 기본템플릿으로도 풀 수 있는 쉬운 문제입니다.

 

(혹시 틀리거나 이해가 안가는 부분이 있으시다면 댓글 남겨주세요~😉)