회문, 팰린드롬(Palindrome) 알고리즘 (with Python3)

Palindrome

팰린드롬은 한국말로 회문이라고 한다.

회문은 거꾸로 읽어도 같은 문자열이 되는 문자열을 말한다. 예를들어서, "mom", "bob", "12321" 과 같은 문자열을 말한다.

 

팰린드롬을 확인하는 방법은 여러가지가 있겠지만, 큐와 스택의 특성을 이용하면 쉽게 찾을 수 있다.

큐는 FIFO 특징을 가지고 있고, 스택은 LIFO 특징을 가지고 있다.

 

큐와 스택에 대한 개념은 아래글을 참고한다.
2020/03/28 - [Algorithm] - 큐(Queue) 와 스택(Stack) 자료구조

로직(Logic)

1. 큐와 스택에 각각 문자열을 담는다.
2. 큐에서 꺼낸값과 스택에서 꺼낸값이 모두 같다면 회문이다.

예를들어서, 12321 이라는 회문이 있을때,

• 큐와 스택에 각각 담는다. => queue: 12321, stack: 12321
• 값을 하나씩 꺼낸다.

큐(Queue)	큐에서 꺼낸 값	스택(Stack)	스택에서 꺼낸값
[2, 3, 2, 1]	1	[1, 2, 3, 2]	1
[3, 2, 1]	2	[1, 2, 3]	2
[2, 1]	3	[1, 2]	3
[1]	2	[1]	2
[]	1	[]	1

 

코딩

위 로직을 따라서 파이썬으로 알고리즘을 작성해보면

# -*- coding: utf-8 -*-

import unittest


def is_palindrome(text):
    """회문(거꾸로 읽어도 같은 문자)인지 확인한다."""
    queue = list()  # FIFO
    stack = list()  # LIFO

    # 큐와 스택에 각각 문자열을 담는다.
    for c in text:
        queue.append(c)
        stack.append(c)

    # 큐와 스택이 모두 비어있을때 까지 반복한다. (`while queue:` 또는 `while stack:` 을 사용해도 됨)
    while queue and stack:
        # 큐에서 꺼낸 값과 스택에서 꺼낸값이 다르면 회문(palindrome)이 아니다.
        if queue.pop(0) != stack.pop():
            return False
    return True


class Exam14(unittest.TestCase):

    def test_palindrome(self):
        self.assertTrue(is_palindrome("mom"))
        self.assertTrue(is_palindrome("기러기"))
        self.assertTrue(is_palindrome("나야나"))
        self.assertTrue(is_palindrome("기러기"))
        self.assertTrue(is_palindrome("bob"))
        self.assertFalse(is_palindrome("1234"))
        self.assertFalse(is_palindrome("blah blah"))


if __name__ == "__main__":
    unittest.main()

 

Reference

• https://thebook.io/006935/part04/ch13/02-01/