Swift) 백준 17609번 회문 - G5

https://www.acmicpc.net/problem/17609

17609번: 회문

문제 풀이: 1초 안에 풀어야 하기에 O(n^2)으로는 풀 수 없으므로 재귀를 이용하여 문제를 풀었다. 투포인터 알고리즘에 일치하지 않는 문자열이 나올 시 다시 해당 함수를 호출하여 일치하지 않는 곳은 건너뛰고 다시 회문인지를 판단하는 방식으로 문제를 해결. 회문이라면 유사회문이고, 다시 유사회문이 나온다면 그 외의 것이기 때문이다.

import Foundation

let t = Int(readLine()!)!

func solution(input: [String], p1: Int, p2: Int, delete: Bool) -> Int {
    var left = p1
    var right = p2
    
    while left < right {
        if input[left] == input[right] {
            left += 1
            right -= 1
        } else {
            if !delete && (solution(input: input, p1: left+1, p2: right, delete: true) == 0 || solution(input: input, p1: left, p2: right-1, delete: true) == 0) {
                return 1
            }
            return 2
        }
    }
    return 0
}

for _ in 0..<t {
    let input = readLine()!
    print(solution(input: Array(input).map{String($0)}, p1: 0, p2: input.count-1, delete: false))
}