[백준 17609번] 회문

문제 링크 >> https://www.acmicpc.net/problem/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를 순서대로 한 줄에 하나씩 출력한다.

 

 

📝 풀이

❌ 첫 번째 풀이

import sys
input = sys.stdin.readline

n = int(input())
words = []
for _ in range(n):
  words.append(input())

result = []
  
for word in words:
  if word == word[::-1]:
    result.append(0)
  else:
    count = 0

    for i in range(len(word)):
      if word[i] != word[::-1][i]:
        count += 1
    if count == 2:
      result.append(1)
    else:
      result.append(2)

print(*result, sep='\n')

 

words를 순회하며 직접 뒤집어본 것과 비교하는 코드였다.

word와 word를 뒤집은 것이 동일하다면 word는 회문이다.

따라서 이 경우에는 result에 0을 삽입했다.

 

word와 word를 뒤집은 것이 동일하지 않다면 각 문자를 하나하나 비교해 다른 횟수를 count에 저장했다.

문자를 하나만 빼 회문을 만들 수 있는 유사회문의 경우 위치가 2개만 다르기 때문에 count가 2이면 1을, 아니면 회문이 될 수 없으므로 2를 삽입했다.

 

위 코드의 경우 시간초과가 난다.

 

✔️ 두 번째 풀이

import sys
input = sys.stdin.readline

def isPalindrome(word, count, start, end):
  while start <= end:
    if word[start] == word[end]:
      start += 1
      end -= 1
    else:
      if count == 0:
        count += 1
        r1 = isPalindrome(word, count, start+1, end)
        r2 = isPalindrome(word, count, start, end-1)
        return min(r1, r2)
      else:
        return count + 1
  return count

n = int(input())

for _ in range(n):
  word = input().strip()
  print(isPalindrome(word, 0, 0, len(word)-1))

 

투포인터를 사용했다.

start는 word의 0번 인덱스 문자를, end는 word의 제일 마지막 인덱스 문자를 가리키도록 했다.

word가 회문인지 평가할 함수 isPalindrome에는 word와 평가 횟수를 판별할 count, 포인터로 사용할 start, end가 주어진다.

 

isPalindrome 안에서 start와 end를 움직인다.

word가 회문일 경우 start와 end의 사이를 좁혀가며 문자를 비교해도 모두 동일하기 때문에 count의 초기값인 0이 리턴된다.

 

word가 유사 회문일 경우에는 우선 word[start]와 word[end]가 같지 않은 순간이 온다.

이때 else문으로 들어가 현재 count가 어떤 값을 가지고 있는지 확인한다.

 

초기의 count가 가지는 값은 0이므로 if문에 걸린다.

여기서는 일단 이곳에 들어왔다는 의미로 count += 1을 해준다.

그리고 word[start]와 word[end]가 같지 않아진 순간이 온 start와 end의 값에 대해 word[start+1:end]와 word[start:end-1]을 대상으로 이 부분 문자열이 회문인지 비교해본다.

 

word[start+1:end]와 word[start:end-1] 중 하나라도 회문인 경우 word는 유사회문이다.

따라서 이때의 count값인 1이 리턴된다.

 

이 경우에도 해당하지 않을 경우 word는 회문도, 유사회문도 아니기 때문에 count에 1을 더한 값을 리턴한다.

count가 0일 경우에만 1을 더해주기 때문에 count + 1의 값은 2가 된다.