[BOJ] Q17609 회문

[BOJ] Q17609 회문

Question

Language: Python

Difficulty: Silver 1

회문 문제를 풀이할때 start, end 두 개의 포인터를 활용한 two-pointer을 활용하는 것이 좋다.

회문 알고리즘

def ifPelindrom(string):
    start=0
    end=len(string)-1
    while start<end:
        if string[start]!=string[end]:
            return False
        start+=1
        end-=1
    return True

python 방식의 회문 알고리즘

def ifPelindrom(string):
    return string == string[::-1]

문제의 경우 문자 1개를 제거해서 유사 회문인지를 판별하는 게 관건이므로, 회문 탐색을 진행하다가 문자가 서로 안 맞는 경우가 발생하면 왼쪽 경우에서 지우는 경우, 오른쪽 경우에서 지우는 경우를 모두 조사해서 유사 회문을 판별한다.

def ifPseudoPelindrom(string, start,end):
    while start <= end:
        if string[start]==string[end]:
            start+=1
            end-=1
        else:
            return False
    return True


check_left=ifPseudoPelindrom(string,start+1,end)
check_right=ifPseudoPelindrom(string,start,end-1)

Solution

def ifPseudoPelindrom(string, start,end):
    while start <= end:
        if string[start]==string[end]:
            start+=1
            end-=1
        else:
            return False
    return True

def ifPelindrom(string):
    start=0
    end=len(string)-1
    while start<end:
        if string[start]==string[end]:
            start+=1
            end-=1
            continue
        
        else:
            check_left=ifPseudoPelindrom(string,start+1,end)
            check_right=ifPseudoPelindrom(string,start,end-1)

            if check_left or check_right:
                return 1
            else:
                return 2

    return 0
    

def solution():
    for string in strings:
        print(ifPelindrom(string))

if __name__ == "__main__":
    num=int(input())
    strings=[list(input().strip()) for _ in range(num)]
    solution()