[Swift 알고리즘] 프로그래머스(Lv.3) - 단어 변환

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 단어 변환" 문제를 풀었습니다.

 

---

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

코딩테스트 연습 - 단어 변환

 

---

풀이

이번 문제는 bfs 문제입니다.

가장 짧은 변환 과정을 찾는 문제기 때문에 bfs를 사용해야 합니다.

 

1. 예외 처리를 진행합니다.

guard words.contains(target), begin != target else { return 0 }

테스트 케이스가 적어서 필수는 아닌 거 같은데요.

아래 로직을 타기 전에 예외 처리를 진행했습니다.

 

target이 word 리스트에 없거나, begin과 target이 같으면 0을 리턴합니다.

 

2. 시작 노드를 설정합니다.

var needChanged: [(str: String, cnt: Int)] = [(begin, 0)]

입력된 begin을 이용해 시작 노드를 설정합니다.

 

3. 현재 노드와 다음 글자들을 비교해 다른 글자수를 구합니다.

다음 노드는 글자수가 1개인 단어만 가능합니다.

그래서 반복문을 이용해 다른 글자수를 구합니다.

 

4. 다음 변환 단어가 target과 같으면 count + 1을 return 합니다.

다음 변환 단어가 target과 같으면 count + 1을 return 합니다.

현재 노드와 target을 비교하는 것이 아니라 다음 노드를 target과 비교하면 시간복잡도 측에서 유리합니다.

 

5. 다음 변환 단어가 target과 다르면 노드에 넣습니다.

target과 다르면 노드에 넣어 변환을 이어서 합니다.

 

감사합니다!

---

전체 코드

import Foundation

func diffCount(_ str1: String , _ str2: String) -> Int {
    let str1 = Array(str1), str2 = Array(str2)
    var count = 0
    for i in 0..<str1.count {
        if str1[i] != str2[i] {
            count += 1
        }
    }
    
    return count
}

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    guard words.contains(target), begin != target else { return 0 }
    
    var needChanged: [(str: String, cnt: Int)] = [(begin, 0)]
    var index = 0
    while !needChanged.isEmpty {
        let node = needChanged[index]
        index += 1

        let word = node.str
        let count = node.cnt
        
        for nextWord in words {
            if diffCount(word, nextWord) == 1 {
                if nextWord == target {
                    return count + 1
                } else {
                    needChanged.append((nextWord, count + 1))
                }
            }
        }
    }
    
    return 0
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.