백준 17609 회문

출처: www.acmicpc.net/problem/17609

분류: 투포인터

---

접근방식

하나를 제거해서 펠린드롬이 될 수 있는 유사 펠린드롬인지까지 확인해야 하는 문제였습니다.

처음에 반례를 생각 못하고 잘못 접근해서 틀렸었는데요, 양쪽 끝(s, e)에서부터 확인하다가 문자가 다를 때,

s+1 문자와 e 문자가 같은지, 아니라면

s문자와 e-1 문자가 같은지 확인하고 

둘다 아니라면 2를 출력하게 했었는데요,

여기의 반례는 baaba 가 됩니다.

s = 0, e = 4 에서 다를 때 s+1와 e 번째 문자는 둘다 a 로 같은데 이때는 유사회문도 될 수 없습니다.

하지만 맨 뒤의 문자 a를 지워서 s == e-1 로 확인하면 유사회문이 되는 걸 확인할 수 있습니다.

따라서 (s+1, e) 와 (s, e-1)  두 경우를 모두 해봐야 예외없이 처리가 가능합니다.

이 처리를 위해서 재귀적으로 해결했습니다.

 

해결방법

func isPalindrome(_ str: [Character], _ s: Int, _ e: Int, _ hasPass: Bool) -> Int {
    var s = s
    var e = e
    while s < e {
        if str[s] == str[e] {
            s += 1
            e -= 1
            continue
        } else if !hasPass {
            return 2
        } else {
            guard e-s > 1 else { return 1 }

            if isPalindrome(str, s+1, e, false) == 1 {
                return 1
            } else {
                return isPalindrome(str, s, e-1, false)
            }
        }
    }
    return hasPass ? 0 : 1
}

for _ in 0..<Int(readLine()!)! {
    let str = Array(readLine()!)
    print(isPalindrome(str, 0, str.count-1, true))
}

 

배운점

시험에서 테스트케이스 없이 예제만 돌려주면 소리소문 없이 딱 틀리고 넘어가기 좋은 문제였다...

정말 많이 실수할 수 있는 부분인 것 같다! 이런 반례를 꼭 기억하자 !!!