팰린드롬 만들기

1. 문제

2. 입출력

3. 입출력 예시

4. 문제 설계

• Dynamic Programming의 유명한 문제인 편집 거리 문제와 유사한 문제라고 생각이 됨.
• 편집 거리 문제와 마찬가지로, 팰린드롬을 만들어야 할 입력받은 문자열을 각각 행과 열에 알파벳들을 배치한 후,
• 같은 문자열에 대해 배치했으므로 주대각선은 모두 더이상 추가해야할 알파벳이 없으므로 모두 0으로 채울 수 있음
• 그리고 이 문제의 경우 편집거리 문제와 값을 채워나가는 방식이 반대로 아래서 부터 채워나가야 함
• 값을 채울 때 조건은 입력 받은 문자열을 str이라고 했을 때, str[i] == str[j]라면, 더이상 채울 알파벳이 없으므로, 해당 알파벳을 제외한 안쪽의 알파벳들이 팰린드롬을 이루면 되므로, 왼쪽 아래 대각선의 값을 복사하면 되고,
• str[i]과 str[j]가 다르다면, 가령, str[i] == b와 str[j] == a인 경우 ba에 a를 붙이거나 ba에 b를 붙이는 두 가지 경우 중 최소값을 선택해야 함
• 그 값은 아래의 값과 왼쪽 값을 비교하여 최소값에 +1 해준 값을 현재 위치에 저장하면 됨
• 따라서, table[i][j] = str을 팰린드롬으로 만들기 위해 추가해야할 문자의 최소 개수
• table[i][j] = str[i] == str[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 str: String = readLine() else { return }
    table = Array(repeating: Array(repeating: 0, count: str.count), count: str.count)
    
    //MARK: - Process
    for i in 0..<str.count {
        table[i][i] = 0
    }
    
    for i in stride(from: str.count - 1, through: 0, by: -1) {
        for j in stride(from: i + 1, to: str.count, by: 1) {
            if str[str.index(str.startIndex, offsetBy: i)] == str[str.index(str.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[0][str.count - 1])
}
solution()

 

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