회문(Palindrome)이란?
문자열이 회문(palindrome)인지 확인해야 하는 상황에서는 재귀(recursion) 기법과 함께 간단한 인덱싱과 사용자 정의 함수를 활용할 수 있습니다.
회문이란 왼쪽에서 오른쪽으로 읽었을 때와 오른쪽에서 왼쪽으로 읽었을 때 각 인덱스에 위치한 문자가 서로 동일한 문자열을 의미합니다. 예를 들어 'MalaM', 'level', 'racecar' 같은 문자열이 대표적인 회문입니다.
재귀는 큰 문제를 잘게 나눈 작은 단위의 결과를 계산한 뒤, 이 결과들을 결합하여 전체 문제의 해답을 도출하는 방식입니다. 회문 검사에서는 문자열의 양 끝 문자를 하나씩 비교하고, 일치할 경우 안쪽 부분 문자열에 대해 자기 자신을 다시 호출하는 방식으로 동작합니다.
예제 코드
def check_palindrome(my_str):
if len(my_str) < 1:
return True
else:
if my_str[0] == my_str[-1]:
return check_palindrome(my_str[1:-1])
else:
return False
my_string = str(input("Enter the string :"))
print("The string is ")
print(my_string)
if(check_palindrome(my_string)==True):
print("The string is a palindrome")
else:
print("The string isn't a palindrome")
실행 결과
Enter the string : MalaM
MalaM
The string is
MalaM
The string is a palindrome
코드 설명
- 'check_palindrome'이라는 이름의 메서드가 문자열을 매개변수로 받습니다.
- 문자열의 길이가 1보다 작으면(즉, 모든 문자를 검사했다면) 'True'를 반환합니다. 이것이 재귀 호출의 종료 조건입니다.
- 그렇지 않은 경우, 문자열의 마지막 문자와 첫 번째 문자가 일치하는지 비교합니다.
- 두 문자가 일치하면, 두 번째 인덱스부터 마지막 인덱스 앞까지의 부분 문자열(슬라이싱 [1:-1]로 양 끝을 제외)에 대해 메서드를 다시 호출합니다.
- 양 끝 문자가 일치하지 않으면 즉시 'False'를 반환합니다.
- 함수 외부에서는 사용자에게 문자열 입력을 요청합니다.
- 입력받은 문자열은 콘솔에 그대로 출력됩니다.
- 입력된 문자열을 매개변수로 전달하여 해당 메서드를 호출합니다.
- 반환값이 'True'이면 해당 문자열이 회문이라는 메시지를 콘솔에 출력합니다.
- 반환값이 'False'이면 회문이 아니라는 다른 메시지를 출력합니다.
동작 원리와 참고 사항
위 코드는 'MalaM'을 입력했을 때 다음과 같은 순서로 재귀가 진행됩니다.
- 1단계: 'M' == 'M' → check_palindrome('ala') 호출
- 2단계: 'a' == 'a' → check_palindrome('l') 호출
- 3단계: 길이가 1이므로 'True' 반환 → 최종적으로 회문 판정
이 방식의 시간 복잡도는 문자열 길이 n에 대해 O(n)이며, 매번 슬라이싱으로 새로운 문자열이 생성되므로 공간 복잡도는 최대 O(n²)까지 늘어날 수 있습니다. 따라서 아주 긴 문자열을 다룰 때는 투 포인터(two-pointer) 기법으로 양 끝 인덱스만 이동하며 비교하는 반복문 방식이 더 효율적일 수 있습니다. 다만 재귀를 활용한 이 접근법은 분할 정복의 개념을 학습하기에 매우 좋은 예제입니다.