프로그래머스 - 단어변환 (String.Index, Array(String) 시간 복잡도 비교 분석) + BFS

이전 포스트에서는 단어 변환 문제를 DFS와 String.Index 타입을 이용하여 문제를 해결했다

이번 포스트에서는 String.Index 타입으로 subscript에 접근했지만 zip과 Array(String)을 이용하는 방법으로 문제를 해결해보고

최종적으로 String.Index와 zip, Array(String)을 통한 문자 비교 방법의 시간 복잡도를 비교 분석해보려고 한다

 

2025.03.19 - [알고리즘 문제(Swift)] - 프로그래머스: 단어 변환(DFS + String.Index)

프로그래머스: 단어 변환(DFS + String.Index)

 

DFS + String.Index (이전 포스트와 동일)

import Foundation

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    var answer = Int.max       // 최소값을 구하기 때문에 Int.max로 할당
    var strCount = begin.count // 단어 길이
    var visited = Array(repeating: false, count: words.count) // 변환한 단어 구분
     // DFS로 구현 (index: 변환 카운트, value: 현재 단어)
    func recur(index: Int, value: String) {
        if value == target {  // 현재 단어와 타겟이 같으면 종료
            answer = min(answer, index) // 정답 값은 기존 변환 카운트와 현재 카운트 중 작은 값으로 할당
            return
        }
        
        // 모든 단어를 순회하면서 변환할 수 있는 단어(알파벳이 하나 차이나는) 찾기
        for i in 0..<words.count {
            let word = words[i] // 비교 문자
            var sameCount = 0 // 같은 문자 개수
            for j in 0..<strCount {
                let valueIndex = value.index(value.startIndex, offsetBy: i) // String.Index 타입으로 변환
                let wordIndex = word.index(word.startIndex, offsetBy: i) // String.Index 타입으로 변환
                if value[valueIndex] == word[wordIndex] { sameCount += 1 } // 해당 위치의 글자가 같으면 sameCount + 1
            }
            
             // 변환할 수 있는 단어이면서 변환하지 않았던 단어이면 재귀 호출
            if sameCount + 1 == strCount && !visited[i] {
                visited[i] = true
                recur(index: index + 1, value: word)
                visited[i] = false
            }
        }
    }
    
    recur(index: 0, value: begin)
    return answer == Int.max ? 0 : answer
}

 

 

index(_:offsetBy:)의 시간 복잡도

Swift String은 UTF-8 기반이므로 index(_:offsetBy:)는 최악의 경우 O(n) (특히 multi-byte 문자 포함 시)

그러나 모든 문자가 ASCII(1-byte)라면 O(1)으로 동작 가능 즉, 최악의 경우 O(n), 최선의 경우 O(1)

 

여기에서 multi-byte문자가 뭘까

Swift의 String은 UTF-8 기반으로 문자의 길이가 고정되지 않고 가변적이다

UTF-8에서 영어 알파벳(ASCII 문자)은 1 바이트(1-byte)이지만,

한글, 일본어, 중국어 등은 3 바이트, 이모지는 4바이트로 인코딩 된다

즉, multy-byte 문자란 UTF-8에서 2바이트 이상 사용하는 문자열을 의미한다

 

 

그렇다면 아래 코드의 시간 복잡도는 어떻게 될까

var sameCount = 0 // 같은 문자 개수
for j in 0..<strCount {
     let valueIndex = value.index(value.startIndex, offsetBy: i) // String.Index 타입으로 변환
     let wordIndex = word.index(word.startIndex, offsetBy: i) // String.Index 타입으로 변환
     if value[valueIndex] == word[wordIndex] { sameCount += 1 } // 해당 위치의 글자가 같으면 sameCount + 1
 }

for j in 0..<strCount{ ... } : O(n)

value.index(value.startIndex, offsetBy: i) : O(1) → value는 알파벳으로 이루어지기 때문

word.index(word.startIndex, offsetBy: i) : O(1) → word는 알파벳으로 이루어지기 때문

 

따라서 O(n) * (O(1) + O(1)) = O(n) 시간 복잡도를 가진다

 

 

DFS + zip

import Foundation

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    var answer = Int.max
    var strCount = begin.count
    var visited = Array(repeating: false, count: words.count)
    
    func recur(index: Int, value: String) {
        if value == target {
            answer = min(answer, index)
            return
        }
        
        for i in 0..<words.count {
            let word = words[i]
            var sameCount = 0
            
            // String -> Array 변환 후 zip을 이용한 각 자리 문자 비교
            zip(Array(value), Array(word)).forEach {
                if $0.0 == $0.1 { sameCount += 1 }
            }
            
            if sameCount + 1 == strCount && !visited[i] {
                visited[i] = true
                recur(index: index + 1, value: word)
                visited[i] = false
            }
        }
    }
    
    recur(index: 0, value: begin)
    return answer == Int.max ? 0 : answer
}

 

 

코드가 훨씬 가독성이 높아지고 이해하기 쉬어졌지만, 전체적으로 소요 시간이 증가되었다

Array(String)으로 문자열을 배열로 초기화하는 과정이 O(n) 시간 복잡도를 가지기 때문에 이 과정이 추가되어 시간 복잡도가 늘어난 것 같다

참고) https://forums.swift.org/t/type-casting-string-to-array/73563

 

Array(Sting)의 시간 복잡도

→ GPT에 따르면, Array(Sting)은 문자열을 순회하면서 Character의 배열로 변환하는 과정이다

Array(String)의 내부 동작

1. String의 각 문자를 순회하면서 Character 단위로 분리
2. 이를 Array<Character>로 변환

문자열 길이를 n이라고 하면,

• 문자열 순회하는 데 O(n)
• 각 문자를 Character 배열에 추가하는 데 O(1) (평균적으로)

결론적으로 전체 시간 복잡도는 O(n)이 된다

 

그렇다면 아래 코드의 시간 복잡도는 어떻게 될까

var sameCount = 0

// String -> Array 변환 후 zip을 이용한 각 자리 문자 비교
zip(Array(value), Array(word)).forEach {
     if $0.0 == $0.1 { sameCount += 1 }
}

Array(value) : O(n)

Array(word) : O(n)

zip(Array(value), Array(word)) : O(n)

forEach {} : O(n)

따라서 O(n) + O(n) + O(n) + O(n) = 4O(n) = O(n) 시간 복잡도를 가진다

 

 

결과적으로 zip과 Array(String)을 사용하는 코드가 String.Index를 사용하는 코드보다 더 큰 시간복잡도를 가지게 되는 것이다

 

 

 

 

ETC - BFS 사용 

(BFS + String.Index)

import Foundation

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    var visited = Array(repeating: false, count: words.count) // 방문 표시
    var queue: [(String, Int)] = [(begin, 0)] // (현재 단어, 변환 횟수) 튜플 배열
    var answer = 0
    
    while true {
        let (str, count) = queue.removeFirst() // 첫 번쨰 요소 추출
        if str == target { // 타겟과 같으면 break
            answer = count
            break
        }
        
        // 현재 단어와 한 글자가 다른 문자열 찾기
        for i in 0..<words.count {
            if visited[i] { continue } // 이미 확인한 단어면 생략
            
            var sameCount = 0 // 같은 글자수 카운트
            for j in 0..<str.count {
                let strIndex = str.index(str.startIndex, offsetBy: j)
                let wordIndex = words[i].index(words[i].startIndex, offsetBy: j)
                if str[strIndex] == words[i][wordIndex] { sameCount += 1 }
            }
            
            // 한글자가 다른 단어면 큐에 추가 및 방문 처리
            if sameCount + 1 == begin.count {
                queue.append((words[i], count + 1))
                visited[i] = true
            }
        }
        
        if queue.isEmpty { break } // 큐가 비면 반복문 종료 (한 글자만 차이나는 단어가 없으면)
    }
    
    return answer
}

 

(BFS + zip)

import Foundation

func solution(_ begin:String, _ target:String, _ words:[String]) -> Int {
    var visited = Array(repeating: false, count: words.count)
    var queue: [(String, Int)] = [(begin, 0)]
    var answer = 0
    
    while true {
        let (str, count) = queue.removeFirst()
        if str == target { 
            answer = count
            break 
        }
        
        for i in 0..<words.count {
            if visited[i] { continue } 
            
            var sameCount = 0
            zip(Array(str), Array(words[i])).forEach {
                if $0.0 == $0.1 { sameCount += 1}
            }
            
            if sameCount + 1 == begin.count {
                queue.append((words[i], count + 1))
                visited[i] = true
            }
        }
        
        if queue.isEmpty { break }
    }
    
    return answer
}