BOJ 17609 회문 [Python 3]

오늘의 문제는 BOJ 17609 회문이다.

 

팰린드롬 (palindrome)은 다른 문제에서도 많이 나오는 주제이다. 기러기, 스위스, 우영우처럼 앞으로 읽어도, 뒤로 읽어도 같은 말을 의미한다.

해당 문제에서는 유사회문을 한 알파벳이 삭제되었을 때 팰린드롬이 되는 것을 유사회문이라고 정의한다.

 

즉, 회문, 유사회문, 기타 3가지로 classify하는 문제이다.

 

t=int(input())
for _ in range(t):
    data=list(input())
    l=len(data)
    i=0
    j=len(data)-1
    diffcount=0
    while i<=j:
        if data[i]==data[j]:
            i+=1
            j-=1
        else:
            if data[i+1:j+1]==data[i+1:j+1][::-1]or data[i:j]==data[i:j][::-1]:
                diffcount=1
            else:
                diffcount=2
            break
    
    print(diffcount)

해당 알고리즘은, 우선 앞 뒤로 pointer를 설정해준다. 이후, diffcount ( 추후에 출력할 예정)을 설정해준다.

계속 greedy하게 확인한다.

1. 앞 뒤 문자가 같은 경우: 인덱스로 넘어간다.

2. 다른 경우: 앞에를 제외한 경우 palindrome일 수도 있고, 뒤에를 제외했을 때 palindrome일 수도 있기 때문에, 둘 다 없애보고 둘 중에 하나 palindrome 인 경우 유사회문, 해당사항 없을 경우 기타이다.