[자료 구조] 회문 찾기 / 큐 & 스택

회문 回文, palindrome
순서대로 읽어도 거꾸로 읽어도, 그 내용이 같은 낱말이나 문장
낱말 사이에 있는 공백이나 문장 기호 등은 무시한다.

 

역삼역, wow, 다가가다, God's Dog 등을 예로 들 수 있다.

 

자료 구조

여러 가지 자료와 정보를 컴퓨터 안에 저장하고 보관하는 방식

주어진 자료를 효율적으로 정리하고 보관하는 것은 알고리즘 문제 풀이의 필수이므로 알고리즘과 자료 구조는 밀접한 관계를 가진다.

 

큐 Queue

사전적으로 줄, 줄을 서서 기다리는 것을 의미한다.

이미지 출처 : https://velog.io/@gillog/%ED%81%90Queue

그 뜻처럼 먼저 저장한 자료를 먼저 빼내는 선입선출(FIFO, First In First Out) 방식의 자료구조다.

큐에 자료를 집어넣는 동작을 enqueue, 큐에서 자료를 빼내는 동작을 dequeue라고 한다.

코드

• 리스트를 이용
  

  # 선언
  qu = []
  
  # enqueue
  qu.append()
  
  # dequeue
  qu.pop(0)​

• collection 모듈 이용
  

  from collections import deque
  
  # 선언
  qu = deque()
  
  # enqueue
  qu.append(1)
  
  # dequeue
  qu.popleft()​

 

스택 Stack

사전적으로 쌓아 올린다는 것을 의미하며, 차곡차곡 쌓아 올린 형태의 자료구조다.

이미지 출처 : https://justicehui.github.io/easy-algorithm/2018/06/03/Stack/

가장 마지막에 저장한 자료를 가장 먼저 빼내는 후입선출(Last In First Out) 방식의 자료구조다.

스택에 자료를 넣는 동작을 push, 스택에서 자료를 빼내는 동작을 pop이라고 한다.

 

코드

# 선언
st = []

# push
st.append()

# pop
st.pop()

 

회문 찾기 알고리즘

문자열을 큐와 스택에 저장한 후, 각각에서 하나씩 빼낸 값이 모두 같으면 회문이다.

 

코드

• 자료구조 사용
  

  def palindrome(str):
      qu = []
      st = []
  
      for x in str:
          if x.isalpha(): # 알파벳만 저장
              qu.append(x.lower())
              st.append(x.lower())
  
      while qu:
          if qu.pop(0) != st.pop():
              return False
      return True​

• 자료구조 미사용
  

  def palindrome(str):
      i = 0          
      j = len(s) - 1
  
      while i < j:   
          if s[i].isalpha() == False:
              i += 1
          elif s[j].isalpha() == False:
              j -= 1
          elif s[i].lower() != s[j].lower():
              return False
          else:
              i += 1
              j -= 1
              
      return True​

 

참고 문서

https://thebook.io/006935/part04/ch13/