[BOJ] 백준 17609번 회문 - 파이썬(Python)

문제

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

입력

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

출력

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

 

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

17609번: 회문

 

💡 풀이 및 코드

string = []
n = int(input())
for _ in range(n):
    string.append(input())

def palindrome(s, e, temp):
    while s <= e:
        if str[s] == str[e]:
            s += 1
            e -= 1
        else:
            if temp == 0:
                left = palindrome(s+1, e, temp+1)
                right = palindrome(s, e-1, temp+1)
                return min(left, right)
            else:
                return 2
    return temp
                
result = []
for str in string:
    s, e = 0, len(str)-1
    result.append(palindrome(s, e, 0))
        
for r in result:
    print(r)

단순 구현 문제이지만 재귀에 대한 복습이 필요할 것 같다.

맨 처음엔 문자열의 시작점을 가리키는 변수 s와 끝점을 가리키는 변수 e에 대하여 s가 가리키는 문자(str[s])와 e가 가리키는 문자(str[e])가 같으면 s+1, e-1로 포인터를 옮겨주고, 만약 두 문자가 다르다면 s와 e가 가리키는 문자가 서로 달랐던 횟수를 나타내는 temp에 따라서 경우를 다시 나눠준다. temp가 1이상이라면 문자 하나를 삭제해도 회문이 안되므로 2를 반환한다. temp가 0이면 재귀를 통해 한번은 s만 s+1로 옮겨 나머지 문자들이 회문인지 판별(left)하고, 또 한번은 e만 e-1로 옮겨주어 회문인지 판별(right)하여 두 경우의 반환값 중 작은 값을 최종 문자열의 반환값 즉, 회문 판별 값으로 선택한다. 예를 들어, s+1로 옮겨 판별한 경우(left) 나머지가 회문이어서 1이, e-1로 옮겨 판별한 경우(right) 나머지가 회문이 아니어서 2가 반환됐다면 이 문자열은 유사회문이므로 1을 반환하게 된다. 이때, 처음부터 회문인 경우에는 temp의 초기값인 0이 그대로 반환된다.