[BOJ] 17609 회문 - python

TIP

문제 링크 (opens new window)

분할정복 + 재귀

문제 요약

입력으로 문자열 S 가 주어질때,

회문(palindrome)인지 유사회문인지 둘다 아닌지를 구해라.

풀이의 큰흐름

1. 일단 S 가 회문인지 검사한다. 만약 회문이 맞다면 0 을 출력한다.
   • is_palindrome(s)
2. S 가 유사 회문인지 검사한다. 유사 회문이 맞다면 1을 출력한다.
   • is_psudo_pal(s)
3. 회문도 아니고 유사회문도 아니므로 2를 출력한다.

1. 회문인지 검사하는 로직

1. 로직
   

   S의 0번째 문자가 마지막 문자와 같지않다면 False 리턴

   S의 1번째 문자가 끝에서 두번째 문자와 같지않다면 False 리턴

   ...

   만약 S[i] != S[len(s) - 1 - i] 이라면 -> False 리턴

   ...

   ( i= len(s)//2) 까지 )

def is_palindrome(s):
    for i in range(len(s)//2):
        if s[i] != s[len(s)-1-i]:
            return False
    return True

2. 코드 개선
   

S[len(s) - 1 - i] 를 좀더 의미가 잘 드러나게 표현할수는 없을까? S[~i]로 표현하면된다!

추가로 설명을 하자면,

i 가 0 이라면 ~i 는 -1 이 된다. S[-1] 은 끝에서 첫번째 문자를 의미하므로 S[len(s) -1 -0] 과 동일한 문자이다.

i가 1 이라면 ~i 는 -2 가 되고, S[-2] 는 끝에서 두번째 문자를 의미하므로 S[len(s) - 1 -1] 와 동일한 문자이다

...

# if s[i] != s[len(s)-1-i] 를 아래 코드로 개선  
if s[i] != s[~i]:

3. 코드를 더 깔끔하게 만들어보자
   

S를 역순으로 만든 문자열과 S 가 같다면 회문이라는 정의를 그대로 구현하면 아래 코드와 같다.

이전 코드보다 코드가 간결하고 의미가 명확하게 드러난다. 속도는 오히려 더 빨라지는것을 볼수있었다.

(BOJ Python3 제출: 252ms -> 148ms)

def is_palindrome(s):
    return s[::-1] == s

2. 유사 회문인지 검사하는 로직

정의를 다시 읽어보자.

S 에서 문자 하나를 제거했을때, 그 문자열이 회문이라면 S 는 유사 회문이라고 볼수있다.

예제를 통해 규칙을 찾아보자.

s='xabba' , 첫번째 위치에서 제거 -> s='abba' (True)

s='abbax' , 마지막 위치에서 제거 -> s='abba' (True)

s='summuus', 네번째 위치('u) 에서 제거 -> s='summus' (True)

s='xabbay' -> (False)

제거되는 위치는 첫번째위치거나 마지막위치거나 문자열 어딘가의 위치임을 알수있다. 이제 문자열 어딘가의 위치라는 것을 구체화 해보자.

예제에서 'summuus' 를 봤을때 첫번째 문자('s') 를 제거할 필요가 없다는 것을 직관적으로 알수있다.

왜냐하면 첫번째 문자('s') 는 반대편 문자('s')와 같기때문이다.

s 에서 첫번째 문자와 반대편 문자는 검사 대상에서 제외된다. 두번째 문자('u') 도 마찬가지 논리가 적용된다.

즉 S 의 범위를 좁혀나가면서 유사 팰린드롬을 구할수있다.

def is_pseudo_pal(a):
    if len(a) == 2:
        return True
    
    # 첫글자 또는 끝글자를 제거해서 팰린드롬인지 
    if is_palindrome(a[1:]) or is_palindrome(a[:-1]):
        return True

    # 첫글자와 끝글자가 다르면서 유사 팰린드롬이 되기위해서는
    # 첫글자 또는 끝글자를 제거해서 팰린드롬이 되는 방법밖에 없다.
    if a[0] != a[-1]:
        return False
    
    # 반대편 문자와 다른 문자를 찾는다. 
    diff_i = 1
    for i in range(1,len(a)//2):
        if a[i] != a[~i]:
            diff_i = i
            break
	
    # ex, a='summuus'이라면, diff_i=2, a[2:~2+1]='mmu'
    return is_pseudo_pal(a[diff_i:~diff_i+1])

전체 소스코드

import sys
input = sys.stdin.readline

def is_palindrome(a):
    return a[::-1] == a

def is_pseudo_pal(a):
    if len(a) == 2:
        return True

    if is_palindrome(a[1:]) or is_palindrome(a[:-1]):
        return True

    if a[0] != a[-1]:
        return False
    diff_i = 1
    for i in range(1,len(a)//2):
        if a[i] != a[~i]:
            diff_i = i
            break

    return is_pseudo_pal(a[diff_i:~diff_i+1])

T = int(input())
for _ in range(T):
    s = input().rstrip()
    ans = 2
    if is_palindrome(s):
        ans = 0
    elif is_pseudo_pal(s):
        ans = 1
    print(ans)