[BOJ/Python] 17609_회문

문체 출처:https://www.acmicpc.net/problem/17609

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를 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

7
abba
summuus
xabba
xabbay
comcom
comwwmoc
comwwtmoc

예제 출력 1

0
1
1
2
2
0
1

 

---

풀이

투 포인터 문제이다. 투 포인터에 대한 설명은 아래 게시물에 작성해 두었다.

 

투 포인터(Two Pointers) 알고리즘

문제에 대한 풀이는 다음과 같다.

1. 양쪽 끝에서부터 시작하여 중간으로 한 칸씩 이동하며 해당 문자가 같은지 확인한다.
2. 같다면 계속 진행하여, 최종적으로 회문이라면 0을 출력한다. (while 왼쪽 포인터 < 오른쪽 포인터)
3. 탐색하는 과정에서 같지 않은 문자가 나온다면, 각각을 제외한 문자열을 생성하여 회문인지 확인한다.
4. 이 경우 둘 중 하나라도 회문이라면 1을 출력하고, 아니라면 2를 출력한다.

예를 들어 summuus가 회문인지, 유사회문인지 둘 다 아닌지 확인하는 경우 다음과 같다.

summuus의 양 끝점부터 비교를 시작한다. s와 s는 같기 때문에 한 칸씩 중간 방향으로 이동한다.

 

마찬가지로 두 포인터가 가리키는 문자가 같기때문에 한 칸씩 중간 방향으로 이동한다.

 

여기서 두 포인터가 가리키는 문자가 다르기 때문에 회문은 될 수 없다.

이제 유사회문(한 문자를 삭제하면 회문이 되는 경우)인지를 확인해야 한다.

• 빨간색 포인터가 가리키는 m을 삭제한 경우
• 파란색 포인터가 가리키는 u를 삭제한 경우

이 두 가지로 경우를 각각 확인하여 한 가지라도 회문이 된다면 원래 문자열이 유사회문임을 알 수 있다.

 

이렇게 두 가지 경우의 문자열을 생성하였다.

첫 번째 경우부터 살펴보면 다음과 같다.

양 끝 점을 비교한다. 같기 때문에 중간 방향으로 한 칸씩 이동한다.

 

마찬가지로 같기 때문에 중간 방향으로 한 칸씩 이동한다.

 

두 포인터가 가리키는 문자가 다르기 때문에 이 경우는 회문이 아니게 된다.

이제 두 번째 경우를 살펴보면 다음과 같다.

두 포인터가 가리키는 문자가 같으므로 가운데 방향으로 한 칸씩 이동한다.

 

마찬가지로 두 포인터가 가리키는 문자가 같으므로 가운데 방향으로 한 칸씩 이동한다.

 

최종적으로 탐색을 모두 마쳤을 때, 다른 문자가 없었기 때문에 이 경우 회문임을 알 수 있다.

따라서 summuus에서 u를 제거하였을 때 회문이므로, summuus는 유사회문이 된다.

 

코드로 작성해 보면 다음과 같다.

 

import sys
 
def isPalindrome(s):
    if s==s[::-1]:
        return True
    else:
        return False
 
 
t = int(sys.stdin.readline())
 
for _ in range(t):
    s = sys.stdin.readline().strip()
    
    start= 0
    end = len(s)-1
    result = 0
    while start<end:
        if s[start]!=s[end]:
            bool1 = isPalindrome(s[:start]+s[start+1:])
            bool2 = isPalindrome(s[:end]+s[end+1:])
            if bool1 or bool2:
                result = 1
                break
            else:
                result = 2
                break
        else:
            start +=1
            end -=1
    print(result)

 

1. isPalindrome 함수의 경우 문자열 s와 문자열 s를 뒤집은 문자열이 같은지(회문인지)를 확인하는 함수이다. 
2. start와 end를 이용하여 양쪽 끝에서부터 문자를 비교하기 시작한다.
3. 만약 start index의 문자와 end index의 문자가 다르다면, 각각을 뺀 문자열을 생성한다.
4. s [:start] + s [start+1:]의 경우 start index를 뺀 문자열이다.
5. 각각의 문자열이 회문인지를 확인하여 둘 중 하나라도 회문이면 유사회문이므로 1을 출력하고, 아니라면 2를 출력한다. (회문도 아니고 유사회문도 아닌 경우)
6. 만약 양쪽 끝에서부터 탐색하였을 때 다른 문자가 없다면 회문이므로 0을 출력한다.