[백준 / python] 17609. 회문

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

17609번: 회문

첫 번째 시도

1개만 제외하고 회문이 되는 경우를 유사 회문이라고 정의할 때, 그 문제가 되는 문자를 찾아서 저장해두고

투포인터로 문자열을 순회하면서 문제가 발생했을 때 사전에 저장한 문제의 문자와 비교하면 되겠다고 가정한 채 구성한 로직이었다.

 

결과는 실패였다. 가정은 그럴싸하였다고 생각했으나, 문제가 되는 문자를 찾는 로직에 오류가 있어서 제대로 문자를 찾아내지 못헀고, 이는 결국 실패로 이어졌다.

import sys
from collections import defaultdict as dd
input = sys.stdin.readline

for _ in range(int(input())):
    cnt, point = 0, -1
    is_palindrom = True
    is_pseudo = False
    s = list(input().strip())
    d = dd(int)
    left = 0
    right = len(s)-1

    for i in s:
        d[i] += 1
    # print(d)
    for i in d.values():
        if (i%2) == 1: cnt += 1
    if cnt >= 2: print(2); continue
    elif cnt == 1:
        for i in d.keys():
            # print(i)
            if (d[i]%2) == 1: point = i
            is_pseudo = True
    # print("point:", point)
    for i in range(len(s)):
        if s[left] == s[right]:
            left += 1
            right -= 1
        elif s[left] != s[right]:
            if s[left] == point: left += 1
            elif s[right] == point: right -= 1
            elif left > right: break
            else: is_palindrom = False; break
        elif left > right: break

    if not is_palindrom: print(2)
    elif is_pseudo: print(1)
    else: print(0)

 

두 번째 시도

문제가 되는 문자 한 개를 찾아낼 수 없다면 우선 한 인덱스를 점프해보고 회문이 되면 OK 라는 가정으로 시작했다.

투포인터를 통해 정상적으로 회문 탐색을 하다가 일치하지 않는 문자가 확인될 경우 우선 점프해보고 회문이 되면 return 1을 하는 구조이다. 하지만 이 또한 구현한 로직에 치명적인 오류가 있었다. 바로 왼쪽부터 점프할 지, 오른쪽부터 점프할 지의 순서에 따라서 구별해낼 수 있는 문자열이 달라진다는 것이다. 따라서 다시 한번 실패를 겪었다.

import sys
from collections import defaultdict as dd
input = sys.stdin.readline

def palindrom(string):
    left = 0
    right = len(string) - 1
    cnt = 0 # 안맞는 문자 세기
    is_pseudo = False
    while True:
        if left >= right: break
        if string[left] == string[right]: left += 1; right -= 1 # 정상 진행
        elif string[left] != string[right]:
            cnt += 1
            is_pseudo = True
            if string[left+1] == string[right]: left += 1
            elif string[left] == string[right-1]: right -= 1
            else: return 2
    if is_pseudo and cnt == 1: return 1
    elif is_pseudo and cnt > 1: return 2
    else: return 0

t = int(input())

for _ in range(t):
    s = input().strip()
    ans = palindrom(s)
    print(ans)

 

세 번째 시도

그렇다면 두 점프의 경우를 모두 체크할 수 있는 로직이 필요하다는 결론에 이르렀다. 두 점프 케이스를 모두 조사하여 둘 중 하나가 성립할 경우 return 1, 둘 다 성립하지 않을 경우 return 2, 그리고 정상적인 회문의 경우 return 0으로 되게끔 하였고, 이는 성공하였다.

import sys
input = sys.stdin.readline

def is_pseudo(string, left, right):
    while True:
        if left > right: break
        if string[left] == string[right]: left += 1; right -= 1
        else:
            return False
    return True
def is_palindrom(string):
    if string == string[::-1]:
        return 0
    else:
        left = 0
        right = len(string) - 1
        while True:
            if left > right: break
            if string[left] != string[right]:
                l_flag = is_pseudo(string,left+1,right)
                r_flag = is_pseudo(string,left,right-1)
                if l_flag or r_flag: return 1
                else: return 2
            else:
                left += 1
                right -= 1

for _ in range(int(input())):
    print(is_palindrom(input().rstrip()))