[BOJ][🟡5][백준#17609] 회문

문제 출처

BAEKJOON Online Judge #17609

문제

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다. 여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

입력

입력의 첫 줄에는 주어지는 문자열의 개수를 나타내는 정수 T(1 ≤ T ≤ 30)가 주어진다. 다음 줄부터 T개의 줄에 걸쳐 한 줄에 하나의 문자열이 입력으로 주어진다. 주어지는 문자열의 길이는 3 이상 100,000 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

출력

각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다.

예제

입력

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

출력

0
1
1
2
2
0
1

My Sol

import sys
input = sys.stdin.readline
from collections import deque
from copy import deepcopy

def check():
    txt = deque(input().rstrip())
    tl = len(txt)
    txt, tl = check2(txt, tl)

    if tl < 2: return 0

    txt_a = deepcopy(txt)
    txt_a.pop()
    txt1, tl1 = check2(txt_a, tl-1)
    if tl1 < 2: return 1

    txt_b = deepcopy(txt)
    txt_b.popleft()

    txt2, tl2 = check2(txt_b, tl-1)
    return 2 if tl2 > 1 else 1


def check2(txt, tl):
    while tl >= 2:
        if txt[0] == txt[-1]:
            txt.pop()
            txt.popleft()
            tl -= 2
            continue
        break
    return txt, tl

T = int(input().rstrip())
for _ in range(T):
    print(check())

deque를 이용해 양 끝의 알파벳이 같다면 하나씩 빼주며 확인하는 방식으로 문제를 해결했다. 한 문제를 제거하는 경우를 고려해야 했기 때문에 만약 양쪽을 제거하다가 일치하지 않는 경우를 만난다면 그 때까지의 deque와 길이를 반환하는 함수 check2를 만든다. 그리고 최초 입력에 대한 deque를 check2에 넣으면 한 번의 회문 체크를 할 수 있다. 여기서 길이가 1 이상이라면 그 자체로 회문이 아닌 상황이다.

만약 그렇다면 해당 deque에 대해 앞의 알파벳을 뺀 경우와 뒤의 알파벳을 뺀 경우에 대해 check2를 다시 돌려 확인하면 되겠는데, 한 경우라도 회문인 경우에는 1, 아니라면 2를 반환해 출력한다.

알 수 없는 이유로 계속 틀려서 힘들게 풀어냈는데, 알고보니 한 번 회문 체크를 마친 txt deque를 두 가지 경우로 check2를 돌리는 경우 txt의 앞 뒤 문자를 빼내고 append 해주었는데, 알고보니 얕은복사가 되어서 두 번째 경우의 체크를 하는 경우에 이전 첫 번째 경우의 체크까지 마친 deque가 들어갔던 것이었다. 이를 파악하고 deepcopy로 변경하자 해결할 수 있었다.

결과

맞았습니다!!

모범답안

출처

from sys import stdin
input = stdin.readline

def is_palindrome(string):
  p1 = 0
  p2 = len(string) - 1

  while p1 < p2:
    if string[p1] == string[p2]:
      p1 += 1
      p2 -= 1
    else:
      tmp1 = string[:p1] + string[p1 + 1:]
      tmp2 = string[:p2] + string[p2 + 1:]
      
      if tmp1[:] == tmp1[::-1] or tmp2[:] == tmp2[::-1]:
        return 1        
      else:
        return 2
  return 0


T = int(input())

for _ in range(T):
  string = input().strip()
  print(is_palindrome(string))

연산시간이 짧은 풀이를 발견해서 분석해보려 한다. 이 분은 index를 이용한 slicing으로 문제를 풀어내셨다. 시간과 공간 복잡도 때문에 되도록 슬라이싱을 지양하는 편인데, 어차피 내가 한 방식이나 이 분 방식이나 배열을 다시 저장하는 방식이라 크게 다름이 없다고 느꼈다.

처음으로 일치하지 않는 순간까지 양쪽의 인덱스를 조정하며 좁혀오다가 일치하지 않는 순간에 인덱스의 조정과 슬라이싱으로 배열을 비교하고, 이에 대한 결과를 반환하여 출력했다. 똑똑한 방식이다.