[백준/17609] 회문 (Python)

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

17609번: 회문

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:25:46

 

---

 

문제 설명

 

회문(回文) 또는 팰린드롬(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

 

 

---

 

풀이

 

투 포인터로 풀이해볼 수 있겠다. 단, 어떠한 상황에서는 분기가 발생하므로, 투 포인터를 큐에 넣고 탐색하는 방식을 사용해보자.

 

• 만약 두 포인터가 가리키는 문자가 같다면 회문의 조건을 충족하므로, 다음 포인터를 그대로 큐에 삽입한다.
• 만약 다르다면, 다음 두 조건을 만족하는 경우를 살펴본다.
  • 왼쪽 포인터와 오른쪽 다음 포인터(right-1)이 가리키는 문자가 같다면, 오른쪽의 현재 포인터 문자를 삭제하고 유사회문으로 취급할 수 있다. 즉 카운터를 1 올리고 왼쪽 다음 포인터(left + 1)와 오른쪽 그 다음 포인터(right - 2)를 큐에 삽입한다.
  • 반대의 경우, 즉 왼쪽 다음 포인터(left + 1)와 오른쪽 포인터가 가리키는 문자가 같다면, 카운터를 1 올리고 왼쪽 그 다음 포인터(left + 2)와 오른쪽 다음 포인터(right - 1)을 큐에 삽입한다.
  • 두 조건이 동시에 만족되는 경우가 존재한다. 이를테면 문자열 "acbac"를 보자. 처음 두 포인터는 a, c를 가리킨다. 첫 번째 조건(a == a), 두 번째 조건(c == c)을 모두 만족하므로, 두 조건 모두 큐에 넣고 탐색해야 한다.
• 만약 조건을 벗어날 경우(왼쪽 포인터가 오른쪽 포인터보다 더 큰 값을 가리키거나, 카운터가 2 이상일때) 탐색을 중지한다. 정상적으로 탐색을 종료한 경우(포인터에 의해 종료된 경우) 카운터값으로 결과를 업데이트한다.

 

풀이 코드

from collections import deque

T = int(input())

for _ in range(T) :
  str = input().strip()
  cnt = 0
  q = deque([(0, len(str)-1, 0)])
  result = 2
  
  while q :
    left, right, cnt = q.popleft()
    print
    if cnt > 2 :
      continue
    if left > right :
      result = min(result, cnt)
      continue
    if str[left] == str[right] :
      q.append((left+1, right-1, cnt))
    else :
      if str[left+1] == str[right] :
        q.append((left+2, right-1, cnt+1))
      if str[left] == str[right-1] :
        q.append((left+1, right-2, cnt+1))
  
  print(result)

풀이 완료!