[백준 17609] 2019 정올 초등부 1차 "회문"

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

17609번: 회문

이 문제는 2019년 정보 올림피아드 1차 초등부 2번 문제였습니다.

회문이란?

회문 또는 팰린드롬이라 불리는 문자열은 드라마 이상한 변호사 우영우를 생각하면 됩니다.

기러기, 토마토, 스위스, 인도인, 별똥별… 이런 단어들처럼 똑바로 읽어도 거꾸로 읽어도 같은 문자열을 회문 이라고 합니다.

유사 회문?

이 문제는 회문을 한 단계 넘어 유사회문이라는 것을 찾아야 합니다. 유사회문은 문자열에서 한 문자를 삭제해서 회문이 되는 경우를 뜻합니다. 문제에서는 영어로 설명했지만 한글로 설명하자면 ‘토메이토’라는 단어를 생각해 보겠습니다. ‘토메이토’는 회문이 아닙니다. 거꾸로 했을 때 ‘토이메토’가 되어 똑같아지지 않습니다. 이 때 ‘이’라는 글자를 빼면 ‘토메토’가 되고, 거꾸로 읽어도 ‘토메토’가 됩니다. 이런 단어들을 유사회문이라고 한 것입니다.

문제 이해하기

회문인지 아닌지 확인하기 위해서는 앞에서 부터 하나씩 맨 뒤쪽 단어와 비교해나가며 회문을 확인하면 됩니다. 그러다 단어가 일치하지 않으면 회문이 아닌 것입니다. 하지만 여기서는 한 단계 더 나아가 유사 회문인지까지 확인해 주어야 합니다. 틀린 글자가 나왔을 때 그 글자를 제거하고 같은지를 확인해 주어야 합니다. 여기서 중요한 것은 그 반대 글자도 확인해야 한다는 것입니다. 예를 들어 보겠습니다.

• accta

위와 같은 단어가 있습니다. 맨 처음부터 비교를 해보겠습니다.

맨 앞의 a와 맽 끝의 a가 같습니다. 첫 번째는 일치하기 때문에 다음으로 넘어갑니다.

다음 c와 t가 다르기 때문에 c를 제거하고 회문인지 확인합니다. acta가 되어 회문이 아님을 알 수 있습니다. 여기서 끝을 내면 안됩니다. 반대쪽 t 역시 제거해서 회문인지 확인해 주어야 합니다. t를 제거하면 acca가 되어 회문이 되고 결국 accta는 유사회문임을 알 수 있는 것입니다.

코드 작성하기

그럼 코드를 직접 작성해 보겠습니다.

입력 받기

T = int(input())

for _ in range(T):
    word = list(input())
    print(solve(word))

먼저 테스트 케이스 T를 입력 받습니다. 다음으로 T번 반복을 하면서 단어 word를 입력 받습니다. 그리고 solve 함수를 통해 word가 회문인지 아닌지를 판단하는 코드 입니다. 그럼 핵심이라 할 수 있는 solve 함수를 알아보겠습니다.

solve 함수

def solve(w):
    N = len(w)

    for i in range(N // 2):
        if w[i] != w[N-1-i]:
            w2 = w[:i] + w[i+1:]
            w3 = w[:N-1-i] + w[N-i:]
            if w2 == w2[::-1] or w3 == w3[::-1]:
                return 1
            else:
                return 2
    return 0

solve 함수는 w라는 단어를 입력 받아 회문임을 판단합니다. 회문을 판단하기 위해서는 글자의 반만 확인하면 됩니다. 왜냐하면 단어의 반을 확인할 때 반대쪽을 같이 확인하기 때문 입니다. 그렇기에 반복문은 N // 2를 해준 것입니다. 혹시나 단어가 홀수일 경우 // 2를 하면 안되지 않을까 생각할 수도 있지만 걱정하지 않아도 됩니다. 단어가 홀수라면 가운데 글자는 비교하지 않아도 되기 때문 입니다. 정 걱정이 된다면 N // 2 + 1로 범위를 잡는 것도 한 방법 입니다.

글자를 하나하나 확인하면서 앞과 뒤가 일치하는지 확인합니다. 마지막 글자의 위치가 N - 1이기 때문에 여기에 -i를 하면 대칭되는 위치의 글자를 확인할 수 있습니다. 파이썬의 경우 w[N-1]과 w[-1]이 같은 뜻입니다. 따라서 w[-1 - i]라고 해도 상관 없습니다.

이렇게 앞과 뒤의 글자들을 비교하다 틀린 글자가 발생하였을 때 이것이 유사회문인지 아닌지를 판단합니다. 먼저 w2는 해당 위치의 글자를 빼주는 것입니다. w[:i]라고 하면 처음부터 i - 1번째 까지의 범위를 가집니다. 다음으로 w[i+1:]이라고 하면 i + 1번째부터 끝까지의 범위를 가지게 됩니다. 즉 원래 단어에서 i번째 글자만 빠지게 되는 것입니다.

파이썬 리스트의 슬라이싱에 대해 잘 모른다면 아래 링크를 확인해 보시기 바랍니다.

https://wikidocs.net/192334#1-

01. 리스트 기본 사용방법

다음으로 w3는 뒤에서 부터 i번째를 뺀 단어 입니다. w[:N - 1 - i]는 처음부터 뒤에서 i + 1 번째까지의 위치 입니다. 그리고 w[N - i:]는 N - i 번째부터 끝까지를 뜻합니다. 결국 N - 1 - i 번째 글자만 제외 한다는 뜻 입니다.

이렇게 만들어진 w2와 w3를 뒤집에서 비교를 합니다. 리스트를 뒤집기 위해서는 list[::-1]을 사용하면 됩니다. 그래서 두 단어들을 비교하여 유사회문이면 1을, 유사회문이 아니면 2를 리턴합니다. 혹시라도 모든 반복을 했음에도 틀린 글자가 아니면 회문이기 때문에 0을 리턴하게 됩니다.

전체 코드

그럼 전체 코드를 확인해 보겠습니다.

T = int(input())

def solve(w):
    N = len(w)

    for i in range(N // 2):
        if w[i] != w[N-1-i]:
            w2 = w[:i] + w[i+1:]
            w3 = w[:N-1-i] + w[N-i:]
            if w2 == w2[::-1] or w3 == w3[::-1]:
                return 1
            else:
                return 2
    return 0

for _ in range(T):
    word = list(input())
    print(solve(word))