백준 17609 : 회문 (Python)

본문 링크

import sys
input=sys.stdin.readline

T=int(input())


def Two_Pointer(start,end,count,answer,P):
    while start<end:
        if string[start]==string[end]:
            start+=1
            end-=1
        elif string[start]!=string[end] and count==0:
            count=1
            if string[start+1]==string[end] and P==0:
                start+=1

            elif string[start]==string[end-1] and P==1:
                end-=1
            else:
                answer=2
                return answer
        else:
            answer=2
            return answer
    if answer==0 and count==1:
        return 1
    else:
        return 0
for i in range(T):
    string=input().rstrip()

    start=0 ; end=len(string)-1 ; count=0 ; answer=0

    answer=min(Two_Pointer(start,end,count,answer,0) ,Two_Pointer(start,end,count,answer,1) )

    print(answer)

📌 어떻게 문제에 접근할 것인가?

유사 회문을 찾기 위해서는 문자열을 결국 전부 탐색하는 수밖에없다.
하지만 문자열의 길이는 3 이상 100,000 이하이므로 $O(N)$ 으로 해결가능한 방법이있을까?

투 포인터를 사용한다면 가능하다. 매번 문자열 하나를 지우면서 하나하나 확인하는것보다
투 포인터를 사용해 같은 문자를 최대한 지운 후 유사회문을 찾는 것이 효율적이다.

📌 어떻게 투 포인터를 사용할 것인가?

start 와 end 값을 잡아준다. 그리고 string[start] 와 string[end] 문자가 같은지 확인해준다. 같다면 start 와 end 값을 이동시킨다.

하지만 투 포인터를 사용하게되면 만약 문자가 다르고 문자 하나를 지울수 있을때
왼쪽의 문자를 지울지 오른쪽의 문자를 지울지 판별불가능하다.

abccbca 라는 문자가있을때 투 포인터를 사용하면
b와 c에서 서로 다르게 된다. 하지만 이때 b를 지워버리면 accbca 가 되고 이는 회문이 아니다.
반면에 c를 지우면 abccba 가 되고 회문이 된다.
따라서 총 2번의 투 포인터 탐색이 필요하다.
임의의 변수 P=0 으로 잡은후 처음에는 왼쪽 문자를 먼저 지우도록 투 포인터를 사용하고
다시 한번 P=1 로 잡은후 오른쪽 문자를 먼저 지우도록 투 포인터를 사용한다.

틀린 문자가 2개이상일경우 2를 반환하고 유사회문이면 1 , 회문이면 0을 반환한다.
answer 은 두 번의 투 포인터중 작은값을 가지고 출력한다.

✅ 코드에서 주의해야할 점

• string 변수는 문자로 입력받으므로 개행문자("\n") 을 지우기 위해 rstrip() 를 사용한다.
• start=0 , end=len(string)-1로 잡는다
• 문자를 한번 지웠는지 확인하는 count 변수를 만들어 준다