[프로그래머스/Swift] 84512번 - 모음사전

문제

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

풀이

• DFS 소스를 먼저짜고 그다음 BFS 소스를 짜서 그런지 BFS가 좀더 깔끔하다

DFS 풀이

• 현재까지의 단어를 word라고 하면 dfs로 AEIOU 하나씩 붙여준다
• 이때 만들어진 단어가 만들고 싶은 단어와 같다면 현재까지 횟수를 저장해서 반환한다
• 이 방법의 장점은 결과를 찾았을때 바로 반환을 해주기에 불필요한 시간을 줄일 수 있다.

BFS 풀이

• A E I O U 를 기본 배열에 넣어두고 while로 배열에 접근한다
• 배열에 접근해서 하나씩 뺀 다음 A E I O U를 하나씩 붙여서 다시 배열에 저장한다.
• 이때 배열의 가장 마지막에 들어간 원소가 UUUUU이면 A~UUUUU까지 배열에 들어간 상태가 된다
• 이후 while을 빠져나온뒤 정렬을 해주고 원하는 단어의 위치를 찾아 반환한다
• 이 방법의 장점은 소스를 짜기 간단하는것이다. 다만 단점은 A를 구하든 AAA를 구하든 A~UUUUU까지를 전부 구하기 때문에 불필요한 시간을 소모할 수 있다.

전체코드

• DFS

import Foundation

func dfs(_ word: [String], _ target: [String], _ tuple: (num: Int, exe: Int)) -> (Int, Int) {
    var result: (Int, Int) = tuple
    if result.0 != -1 { return result } // 결과값이 이미 나왔으면 반환
   
    if check(word, target) {  // 찾고자 하는 값이 같은지
		result.0 = result.1 // 현재까지 횟수를 넣음
    } 
    if word.count < 5 {
        result = dfs(word+["A"], target, (result.0,result.1+1))
        result = dfs(word+["E"], target, (result.0,result.1+1))
        result = dfs(word+["I"], target, (result.0,result.1+1))
        result = dfs(word+["O"], target, (result.0,result.1+1))
        result = dfs(word+["U"], target, (result.0,result.1+1))
    }
    return result
}
func check(_ w1: [String], _ w2: [String]) -> Bool {
    if w1.count != w2.count { return false }
    for value in zip(w1, w2) {
        if value.0 != value.1 { return false }
    }
    return true
}

func solution(_ word:String) -> Int {
	let target: [String] = word.map{ String($0) }
    return dfs([], target, (-1,0)).0
}

• BFS

func solution(_ word:String) -> Int {
    return bfs(word)
}

func bfs(_ target: String) -> Int {
    var queue: [String] = ["A","E","I","O","U"]
    var idx: Int = 0
    
    while queue.last != "UUUUU" {
        let str = queue[idx]
        queue.append(str+"A")
        queue.append(str+"E")
        queue.append(str+"I")
        queue.append(str+"O")
        queue.append(str+"U")
        idx += 1
    }
    queue.sort(by: <)
    for (i,str) in queue.enumerated() {
        if str == target {
            return i+1
        }
    }
    return -1
}