백준 17609 회문 (파이썬)

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

첫번째 풀이 (시간초과)

import sys
def solve():
    string = input().strip()
    if len(string)%2 == 0:
        #뒤집었는데 똑같은 경우
        #그 외는 없음
        left = list(string[:len(string)//2])
        right = list(string[len(string)//2:])
        right.reverse()
        if left == right:
            return 0
        return 2
    else:
        for i in range(len(string)):
            temp = string[:i] + string[i+1:]
            left = list(temp[:len(temp) // 2])
            right = list(temp[len(temp) // 2:])
            right.reverse()
            if left == right:
                return 1

        return 2
if __name__ =="__main__":
    input = sys.stdin.readline
    N = int(input())
    for i in range(N):
        print(solve())

홀수 짝수 경우를 나눠 절반을 역순으로 바꿔 비교해서 풀었습니다. 

홀수인 경우 모든 문자열을 하나씩 제거해가며 절반을 역순으로 바꿔 비교했습니다. 

시간 복잡도는 생각 안하고 요령피워서 비효율적으로 코드를 짠 것 같고 아직 실력이 많이 부족하다는 것을 깨달았습니다. 

그리고 나중에 반례를 찾아 넣어보니 'abcbad' 처럼 짝수 길이의 유사회문이 되는 경우를 처리하는 못하는 틀린 코드였습니다. 

두번째 풀이 (시간초과)

import sys
def Check(half, string):
    for i in range(half):
        if string[i] != string[-(i + 1)]:
            return 2
    return 0
def solve():
    string = input().strip()
    if len(string)%2 == 0:
        half = len(string) // 2
        # 홀수가 나올 수도 있음
        result = Check(half, string)
        if result == 2:
            for i in range(len(string)):
                temp = list(string)
                temp.pop(i)
                half = len(temp) // 2
                if Check(half, temp) == 2:
                    continue
                else:
                    return 1
            return 2
        else:
            return 0
    else:
        for i in range(len(string)):
            temp = list(string)
            #temp = string[:i] + string[i+1:]
            temp.pop(i)
            half = len(temp) // 2
            if Check(half, temp) == 2:
                continue
            else:
                return 1
        return 2
if __name__ =="__main__":
    input = sys.stdin.readline
    N = int(input())
    for i in range(N):
        print(solve())

나름 최적화 했다고 생각했습니다. 하지만 pop이라는 함수는 O(N) 시간 복잡도가 발생하기 때문에 reverse가 없어도 이 역시 시간초과가 발생했습니다.

세번째 풀이 (투포인터)

import sys
def pseudoCheck(string, left, right):
    while left < right:
        if string[left] != string[right]:
            return 2
        else:
            left += 1
            right -= 1
    return 1

def solve():
    string = input().strip()
    left = 0
    right = len(string)-1
    # 만약 left > right : 이는 회문
    while left < right:
        if string[left] != string[right]:
            if pseudoCheck(string, left + 1, right) == 2:
                if pseudoCheck(string, left, right-1) == 2:
                    return 2
                else:
                    return 1
            else:
                return 1
        else:
            left += 1
            right -= 1
    return 0
if __name__ =="__main__":
    input = sys.stdin.readline
    N = int(input())
    for i in range(N):
        print(solve())

두번째 까지 정답을 맞지 못해 결국 검색의 도움을 받았습니다. 검색에서 투 포인터라는 방법을 사용했는데 처음의 왼쪽 위치만 저장하는 것이 아니라 맨 뒤도 같이 값을 비교하면서 두개의 포인터가 가운데로 교차할 때 까지 비교하는 방법이었습니다.  

투 포인더는 퀵 정렬할 때 많이 사용하는 방법인데 회문에도 사용된다고 생각하니 새로웠습니다. 

문제는 어려웠지만 투 포인터라는 개념과 왜 사용하는 지를 한번에 이해한 것 같아 의미있는 문제였습니다.