백준 17609 회문 (파이썬 / 문자열)

17609번: 회문 (acmicpc.net)

17609번: 회문

골드5문제였다.....

처음에는 쉬운 줄 알았다. 바로 통과 아니야? 했다.. 하지만 우여곡절이 정말 많았다.

<첫 번째 코드>

from collections import deque
T = int(input())
for i in range(T):
    str = deque(input())
    stat = 0
    while str:
        if str[0] != str[len(str) - 1]:
            if str[1] == str[len(str) - 1]:
                str.popleft()
            elif str[0] == str[len(str) - 2]:
                str.pop()
            else:
                stat = 2
                break
            stat = 1
        else:
            str.popleft()
            if str:
                str.pop()
    print(stat)

방법은 str을 deque으로 만들어서 str이 없어질 때까지 맨 앞과 뒤를 비교해서 같으면 없애고 다르면 그 옆에있는 값들을 비교해서 깎아내려가는 것이었다.

문제) abbab같은 옆의 문자와 비교해야할 문자가 같은 경우 성립할 수 없었다.

 

<두 번째 풀이>

from collections import deque
T = int(input())

def rout(str, start, end):
    st = True
    for i in range((len(str)) // 2):
        if str[i + start] != str[end - i]:
            st = False
            break
    return st

for i in range(T):
    str = deque(input())
    stat = 0
    while str:
        if str[0] != str[len(str) - 1]:
            if rout(str, 1, len(str) - 1):
                str.popleft()
            elif rout(str, 0, len(str) - 2):
                str.pop()
            else:
                stat = 2
                break
            stat += 1
        else:
            str.popleft()
            if str:
                str.pop()
    print(stat if stat < 2 else 2)

위의 문제를 해결하기 위해서 각각의 if문에 들어갈 때마다 이 안에 있는 값들이 회문인지를 for문을 돌리며 검사하는 코드를 짰다.

문제) 예상하기도 했지만 이중 for문을 돌기 때문에 시간초과가 떴다.

 

<정답 코드>

다른 블로그에서 해답을 찾았다.

import sys
def rot(str):
    left = 0
    right = len(str) - 1
    while left < right:
        if str[left] == str[right]:
            left += 1
            right -= 1
        else:
            if left < right - 1:
                temp = str[:right] + str[right + 1:]
                if temp[:] == temp[::-1]:
                    return 1
            if left + 1 < right:
                temp = str[:left] + str[left + 1:]
                if temp[:] == temp[::-1]:
                    return 1
            return 2
T = int(input())
for i in range(T):
    print(rot(sys.stdin.readline().strip()))

난 아직 이러한 방식으로 코드를 짜 본적이 별로 없지만 비슷한 형태를 목격한 적이 있다.

바로 퀵소트같은 알고리즘에서이다.

left, right로 양 끝의 index를 참조해가면서 left와 right가 교차되기 전까지 조건에 맞게 문자 하나를 빼 가면서 그 상태에서 회문이 가능하다면 1을, 불가능하다면 2를, 처음부터 회문이 된다면 0을 하는 방식이다.

(그래서 이 문제의 유형이 두 포인터 이기도 하다.)

 

또한, str[::]와 같은 방식을 사용하려면 deque를 쓸 수 없다는 것도 알았다..

나중에 문제 풀 때 잘 참조하자...