백준 17609 - (python)회문

www.acmicpc.net/problem/17609

17609번: 회문

 

1. 알고리즘 유형

투포인터

 

2. 자료구조

x

 

3. 풀이

 

회문판단

1) 문자열 왼쪽끝, 오른쪽끝 인덱스 잡고 비교

2) 왼쪽끝과 오른쪽끝이 같아지거나, 크로스 될때까지 문자비교

3) 만약 다르다면 유사회문일 수도 있음, 이상없으면 회문

 

유사회문 판단

1) 왼쪽 인덱스를 한칸 넘겨서 회문인지 판단

2) 오른쪽 인덱스를 한칸 넘겨서 회문인지 판단

3) 1, 2 과정이 둘다 아닌 경우 2를 리턴(아무런 회문이 아니다)

 

회문과 유사회문 판단은 코드 중복이 많으므로 재귀를 사용하여 판단.

type 파라미터를 통해 유사회문 판단인지 회문판단인지 구별

 

코드.

def check(left, right, type):
    ret = type
    while( left < right ):
        if str[left] != str[right] and type == 0:
            a = check(left+1, right, type+1)
            b = check(left, right-1, type+1)
            ret = min(a, b)
            return ret
        elif str[left] != str[right] and type == 1:
            return 2
        else:
            left += 1
            right -= 1
    return ret



N = int(input())
for _ in range(N):
    str = input()
    print(check(0, len(str)-1, 0))