회문(Palindrome)이란 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 의미합니다. 예를 들어 "level", "madam", "racecar" 같은 문자열이 대표적인 회문입니다.
스택(Stack) 자료구조를 활용하면 문자열이 회문인지 손쉽게 판별할 수 있습니다. 스택은 LIFO(Last In, First Out, 후입선출) 방식으로 동작하기 때문에, 문자열의 각 문자를 순서대로 push한 뒤 pop하면 문자열이 자연스럽게 거꾸로 뒤집힙니다. 이렇게 얻은 뒤집힌 문자열을 원래 입력값과 비교하면 회문 여부를 알 수 있습니다.
이를 위해 먼저 스택 클래스를 생성하고, 값을 추가하는 push 메서드와 삭제하는 pop 메서드를 정의합니다. 아울러 스택이 비어 있는지 확인하는 별도의 메서드도 함께 만듭니다.
아래는 실제 동작 과정을 보여주는 예제입니다.
예제 코드
class Stack_structure:
def __init__(self):
self.items = []
def check_empty(self):
return self.items == []
def push_val(self, data):
self.items.append(data)
def pop_val(self):
return self.items.pop()
my_instance = Stack_structure()
text_input = input('문자열을 입력하세요... ')
for character in text_input:
my_instance.push_val(character)
reversed_text = ''
while not my_instance.check_empty():
reversed_text = reversed_text + my_instance.pop_val()
if text_input == reversed_text:
print("입력한 문자열은 회문입니다")
else:
print("입력한 문자열은 회문이 아닙니다")
실행 결과
문자열을 입력하세요... MalayalaM
입력한 문자열은 회문입니다
코드 설명
'Stack_structure'라는 이름의 클래스가 정의되며, '__init__' 생성자 메서드가 포함되어 있습니다.
'__init__' 메서드는 내부적으로 빈 리스트를 초기화하여 스택 저장소 역할을 합니다.
'check_empty' 메서드는 스택이 비어 있는지 여부를 확인합니다.
'push_val' 메서드는 전달받은 데이터를 스택에 추가(append)합니다.
'pop_val' 메서드는 스택에서 가장 마지막에 들어간 요소를 제거하고 반환합니다.
'Stack_structure' 클래스의 인스턴스가 생성됩니다.
input() 함수를 통해 사용자로부터 검사할 문자열을 입력받습니다.
for 반복문으로 문자열을 한 글자씩 순회하며 각 문자를 스택에 push합니다.
빈 문자열 변수(reversed_text)를 하나 선언한 뒤, while 문에서 스택이 빌 때까지 pop을 반복하여 문자열을 뒤집습니다.
pop된 문자들이 순서대로 이어지면서 뒤집힌 문자열이 완성되고, 이 값이 reversed_text에 저장됩니다.
뒤집힌 문자열과 사용자가 입력한 원본 문자열을 비교합니다.
두 문자열이 동일하면 회문으로 판단합니다.
동일하지 않다면 회문이 아닌 것으로 판단합니다.
판별 결과가 콘솔 화면에 출력됩니다.
추가 참고 사항
이 방식의 시간 복잡도는 O(n)으로, 문자열 길이에 비례하여 처리 시간이 증가합니다. 대소문자를 구분하므로 "MalayalaM"처럼 앞뒤가 대칭을 이루는 형태여야 회문으로 인식된다는 점에 유의하세요. 만약 대소문자를 무시하고 싶다면 비교 전에 lower() 메서드를 활용해 두 문자열을 모두 소문자로 변환한 뒤 비교하면 됩니다.