[baekjoon] 백준 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 이하이고, 영문 알파벳 소문자로만 이루어져 있다.

 

알고리즘

- 회문을 판단하는 함수와 유사회문을 판단하는 함수를 만든다.

- 두 함수는 문자열 시작부터 끝까지를 비교하는 함수로 시작과 끝이 크로스 될 때까지 비교한다.

- 시작과 끝의 문자가 같으면 가운데를 향하게 한 칸씩 이동하여 다시 비교한다.

- 시작과 끝의 문자가 다르면 회문은 아님으로 유사회문인지 비교하기 위해 두 케이스로 나누어 유사회문 함수를 통해 확인한다.

- 회문 함수와 유사회문 함수는 마지막 코드 빼고는 같다.

- 회문 함수는 회문이거나 그 외인 것을 확인하는 것이고 유사회문 함수는 유사회문이거나 그냥 문자열인지를 확인하는 차이만을 갖고 있다.

코드

import sys


# 회문 판단 함수
def palindrome(s, start, end):
    # 문자열 시작부터 끝까지, 끝부터 시작까지 비교하고 크로스 되면 멈춘다.
    while start < end:
        # 문자열 시작 문자와 끝 문자가 같으면 한칸씩 가운데를 향하게 이동해 다시 비교한다.
        if s[start] == s[end]:
            start += 1
            end -= 1
        # 시작 문자와 끝 문자가 다르면 회문은 아닌 것이 되고 유사회문인지 확인해야 한다.
        else:
            # 시작 문자를 하나 제거한 케이스와 끝 문자를 하나 제거한 케이스
            # 위 두 가지 케이스를 나누어 유사회문인지 확인한다.
            case1 = pseudo_palindrome(s, start + 1, end)
            case2 = pseudo_palindrome(s, start, end - 1)

            # 두 케이스중 하나라도 True가 나오면 유사회문이다.
            if case1 == True or case2 == True:
                return 1
            # 그게 아니라면 그냥 문자열이다.
            else:
                return 2

    # 문자열 시작 문자와 끝 문자가 크로스 되고도 문자가 서로 같다면 회문이다.
    return 0


# 유사회문 판단 함수
def pseudo_palindrome(a, start, end):
    # 문자열 시작부터 끝까지, 끝부터 시작까지 비교하고 크로스 되면 멈춘다.
    while start < end:
        # 문자열 시작 문자와 끝 문자가 같으면 한칸씩 가운데를 향하게 이동해 다시 비교한다.
        if a[start] == a[end]:
            start += 1
            end -= 1
        # 시작 문자와 끝 문자가 다르면 그냥 문자열이다.
        else:
            return False

    # 문자열 시작 문자와 끝 문자가 크로스 되고도 문자가 서로 같다면 유사회문이다.
    return True


t = int(sys.stdin.readline())
for i in range(t):
    c = list(input())

    # 문자열에 시작과 끝을 확인한다.
    res = palindrome(c, 0, len(c) - 1)

    # 리턴 값 출력
    print(res)

github

junjange/CodingTest