99클럽 코테 스터디 4기 7일차 TIL - 프로그래머스: 모음 사전(84512) Swift & Python

레일리·2024년 11월 3일

99클럽 코테 스터디 4기

목록 보기

7/18

ℹ️ 문제 정보

플랫폼	번호	제목	유형	난이도	언어
프로그래머스	84512	모음 사전	완전탐색	Lv.2	Swift, Python

🚀 나의 접근 방법

이 문제는 완전탐색 문제로 백트래킹(BackTracking)으로 해결할 수 있다. 물론 이외의 방법으로도 문제를 해결할 수 있다.

백트래킹의 핵심은 완전탐색 중에 한정 조건에 부합하지 않으면 이전으로 돌아가 다음 것을 탐색하는 것이다. DFS나 BFS와 함께 구현할 수 있다.

A부터 UUUUU까지 DFS로 탐색하면서 count를 세고, 찾고자 하는 단어에 도달하면 탐색을 멈추도록 했다. 탐색 과정 중에는 백트래킹 기법을 사용하여 찾고자 하는 단어가 아니거나 5자리이면 이전 노드로 돌아가도록 했다.

✍️ 나의 코드

Swift

import Foundation

func solution(_ word:String) -> Int {
    let charList = ["A", "E", "I", "O", "U"]
    var count = 0
    
    func bt(_ result: String) -> Bool {
        count += 1
        
        if result == word {
            return true
        }
        
        if result.count == 5 {
            return false
        }
        
        
        for char in charList {
            if bt(result + char) {
                return true
            }
        }
        
        return false
    }
    
    for char in charList {
        if bt(char) {
            return count
        }
    }
    
    return 0
}

Python

def solution(word):
    charList = ["A", "E", "I", "O", "U"]
    count = 0
    
    def bt(result):
        nonlocal count
        count += 1
        
        if result == word:
            return True
        if len(result) == 5:
            return False
        
        for char in charList:
            if bt(result + char): 
                return True
    
    for char in charList:
        if bt(char):
            return count