[BOJ/PYTHON] 23304.아카라카

백준 문제 링크: https://www.acmicpc.net/problem/23304

핵심 아이디어

재귀로 풀면 된다. 현재 보는 문자열이 팰린드롬인지 체크하고, 맞다면 그 절반을 확인하면 된다.

왼쪽에서 절반과 오른쪽에서의 절반이 동일하다면 둘 중 하나(동일하니까)를 재귀를 돌리면 된다.

오른쪽 절반의 경우 string[half_len :]으로 한다면 홀수, 짝수인 경우의 수를 나눠 string[half_len + 1 :]도 커버해 줘야 하기 때문에 그냥 뒤에서부터 봐서 string[-half_len :]으로 했다.

풀이

# silver2-23304. 아카라카

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

# 주어진 문자열이 아카라카 팰린드롬인지 아닌지 출력
# 아카라카 팰린드롬: 팰린드롬(거꾸로 뒤집어도 같은 문자열)인데 1/2 길이의 접두사와 접미사가 모두 팰린드롬

s = input().rstrip()

def is_akaraka_pallendrom(string):
    if len(string) == 1: return True
    half_len = len(string) // 2
    if string != string[::-1]:
        return False
    left = string[: half_len]
    right = string[-half_len :]
    if left != right:
        return False
    if not is_akaraka_pallendrom(left): 
        return False
    
    return True

if is_akaraka_pallendrom(s):
    print("AKARAKA")
else: print("IPSELENTI")

Trouble Shooting

half_len을 구하는 로직을 재귀함수 안에 넣어야 했는데 그러지 않고 인풋 받고 절반을 구해버려서 절반 길이가 고정되어 재귀를 계속 돌았다.

실행 시간

메모리 36628KB, 시간 72ms (python3)