백준 23304번 아카라카 (Python)

문제

• 문제

AKARAKA(아카라카)는 컴퓨터 과학적 관점으로 바라봤을 때, 튜링도 기립 박수를 치고 갈 가히 최고의 구호라 할 수 있다. AKARAKA는 그 자체로도 팰린드롬이고, 접두사이자 접미사인 AKA가 또한 팰린드롬이기 때문이다.

신촌에서는 AKARAKA같은 특성을 가진 팰린드롬을, 아카라카 팰린드롬이라 아래와 같이 정의한다.

문자열 S가 팰린드롬이다. 팰린드롬이란 거꾸로 뒤집어 읽어도 같은 문자열을 뜻한다.
문자열 S의 길이를 |S|라 할 때, 
 
$\lfloor\frac{|S|}{2}\rfloor$ 길이의 접두사와 접미사가 모두 아카라카 팰린드롬이다. 만약 
|S| = 1이면, 
S는 아카라카 팰린드롬이다.
임의의 문자열이 주어졌을 때, 그 문자열이 아카라카 팰린드롬인지 알아보자. 만약 알아내지 못하면, 졸업할 때까지 아카라카를 못 갈지도 모른다!

• 입력과 출력

입력
알파벳 소문자로 이루어진 문자열 
S가 주어진다. (1 <= |S| <= 2000000)

출력
주어진 문자열 
S가 아카라카 팰린드롬이라면, AKARAKA를 출력한다.
만약 그렇지 않다면, IPSELENTI를 출력한다.

문제 해결 접근

• python으로 풀기 때문에 문자열을 뒤집어서 같은지 체크해보는 것은 슬라이싱으로 쉽게 해결 가능
• 처음에는 문자열 전체, 접두사, 접미사가 각각 아카라카 팰린드롬인지 한번만 확인해보면 될 것이라고 생각 -> 테스트 케이스에서 생각해내지 못했음
• 그런데 문제 이해를 잘 해야 하는 것이, 접두사와 접미사도, 그러니까 재귀적으로 계속 아카라카 팰린드롬인지 확인해야 한다. -> 히든 테스트 케이스! 이 부분을 생각해내는 것이 맞추는 것의 핵심이다.

정답 코드

import sys

S = sys.stdin.readline().strip()

## 아카라카 팰린드롬인지 아닌지 확인하는 함수 
## 재귀적으로 들어가서 prefix와 suffix가 각각 아카라카 팰린드롬인지 확인하기 

def check (S):
  ## S의 길이가 1이면 아카라카 팰린드롬
  if len(S) == 1:
    return True
  
  prefix = S[:len(S) // 2]
  suffix = S[len(S) // 2:] if len(S) % 2 == 0 else S[len(S) // 2 + 1:]
  
  ## 만약에 아카라카 팰린드롬이라면, prefix와 suffix도 팰린드롬인지 확인하기 
  if S == S[::-1] and prefix == prefix[::-1] and suffix == suffix[::-1]:
    return check(prefix) and check(suffix)
  ## 만약에 아카라카 팰린드롬이 아니면, 바로 False를 출력하기 
  else:
    return False


if check(S):
  print('AKARAKA')
else:
  print('IPSELENTI')

문제를 헤매고 있다면,,

• 아마 이 문제에서 틀리고 있다면 (나처럼,,,,) 아래의 예시들을 입실렌티라고 잘못 판단하고 있을 경우가 많다. (백준 질문게시판 참조)

다음 문자열들은 '아카라카 팰린드롬'이 아니다.

WA를 받았다면 아래 예시에서 잘못된 답을 출력하고 있을 것으로 예상된다.

'abcbaabcba'

'abcdcbaabcdcba'

'abba'

• 왜 아닌지에 대한 설명

abcbaabcba의 경우 abcba라는 펠린드롬 접미/접두사를 가지고 있긴하지만, abcba는 아카라카펠린드롬은 아니네요

아카라카펠린드롬은 접미/접두사도 아카라카여야한다고 나와있네요

• 그러면 아마 처음의 나처럼 이런 코드를 제출해보고 있을 가능성이 있다.

import sys

S = sys.stdin.readline().strip()

if len(S) == 1:
  print('AKARAKA')

else:
  prefix = S[:len(S) // 2]
  suffix = S[len(S) // 2:] if len(S) % 2 == 0 else S[len(S) // 2 + 1:]

  if S == S[::-1] and prefix == prefix [::-1] and suffix == suffix [::-1] :
    print('AKARAKA')
  else:
    print('IPSELENTI')

• 위의 코드는 길이가 1인 경우와, 길이가 홀수/짝수인 경우의 케이스만 생각하고 1번만 아카라카 팰린드롬을 확인하고 있다.
• 하지만, 정답 코드와 같이 prefix와 suffix를 재귀적으로 체크하여 아카라카 펠린드롬이 되는지 확인하는 것이 필요하다.

테스트 케이스만으로 문제를 이해하는 것이 아니라, 문제를 잘 이해해서 히든 테스트 케이스도 풀 수 있는지 확인하는 꼼꼼함이 필요하다!