두 문자열 사이의 거리

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• 위 문제의 경우 유명한 편집거리 알고리즘과 유사한데, 다른 점은 삽입, 삭제, 교체 연산중 삽입, 삭제 두 가지 연산만 존재한다는 점
• 따라서 A 문자열의 알파벳들을 행으로, B 문자열의 알파벳들을 열로 배치했을 때, 발생할 수 있는 연산에 대해 저장해 나가는 동적 계획법 알고리즘을 사용할 수 있음
• 먼저, A[i] == B[j] 라면, 더 이상 수행해야할 연산이 없으므로, 왼쪽 대각선 위에서 값을 그대로 복사하면 되고,
• A[i]와 B[j]가 같지 않다면, table[i][j]의 위의 값 + 1인 삭제 연산한 값과, 왼쪽 값 + 1인 삽입 연산한 값 중 작은 값을 현재 table[i][j]에 저장하면 됨
• 따라서, table[i][j] = A[0 ~ i]에서 B[0 ~ j]를 만들기 위해 삽입/혹은 삭제 연산에 대한 최소값이며,
• table[i][j] = A[i] == B[j], table[i - 1][j - 1]이고, 아니라면, min(table[i - 1][j], table[i][j - 1]) + 1의 점화식을 구할 수 있고,
• 문제의 크기 1000을 n이라고 했을 때, O(n^2)의 시간복잡도로 문제를 해결할 수 있음

5. 전체 코드

//MARK: - 두 문자열 사이의 거리

//MARK: - Framework
import Foundation

//MARK: - Variable
var table: [[Int]] = []

//MARK: - Function
func solution() -> Void {
    //MARK: - Input
    guard let A: String = readLine() else { return }
    guard let B: String = readLine() else { return }
    
    table = Array(repeating: Array(repeating: 0, count: B.count), count: A.count)
    
    //MARK: - Process
    for i in 0..<A.count {
        table[i][0] = i
    }
    
    for i in 0..<B.count {
        table[0][i] = i
    }
    
    for i in 1..<A.count {
        for j in 1..<B.count {
            if A[A.index(A.startIndex, offsetBy: i)] == B[B.index(B.startIndex, offsetBy: j)] {
                table[i][j] = table[i - 1][j - 1]
            } else {
                table[i][j] = table[i - 1][j] < table[i][j - 1] ? table[i - 1][j] + 1 : table[i][j - 1] + 1
            }
        }
    }
    
    //MARK: - Output
    print(table[A.count - 1][B.count - 1])
}
solution()

 

전체코드는 여기에서 확인할 수 있습니다.