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

레일리·2024년 11월 3일
0
post-thumbnail

ℹ️ 문제 정보

플랫폼번호제목유형난이도언어
프로그래머스84512모음 사전완전탐색Lv.2Swift, 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

🤔 회고 및 개선사항

기존에 DFS나 BFS 문제는 경험해 보았지만 이를 활용한 백트래킹 문제는 처음 접하였다. 그래서 아직 익숙하지 않아 더 많은 문제를 풀어볼 필요가 있을 것 같다.

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

profile
나야, 개발자
post-custom-banner

0개의 댓글