규도자 개발 블로그

[해커랭크(Hackerrank)/30 Days of Code/파이썬3(python3)] Day 18: Queues and Stacks 본문

알고리즘/풀이

[해커랭크(Hackerrank)/30 Days of Code/파이썬3(python3)] Day 18: Queues and Stacks

규도자 (gyudoza) 2020. 2. 18. 13:08

Welcome to Day 18! Today we're learning about Stacks and Queues. Check out the Tutorial tab for learning materials and an instructional video!

palindrome is a word, phrase, number, or other sequence of characters which reads the same backwards and forwards. Can you determine if a given string, , is a palindrome?

To solve this challenge, we must first take each character in enqueue it in a queue, and also push that same character onto a stack. Once that's done, we must dequeue the first character from the queue and pop the top character off the stack, then compare the two characters to see if they are the same; as long as the characters match, we continue dequeueing, popping, and comparing each character until our containers are empty (a non-match means  isn't a palindrome).

Write the following declarations and implementations:

  1. Two instance variables: one for your , and one for your .
  2. void pushCharacter(char ch) method that pushes a character onto a stack.
  3. void enqueueCharacter(char ch) method that enqueues a character in the  instance variable.
  4. char popCharacter() method that pops and returns the character at the top of the  instance variable.
  5. char dequeueCharacter() method that dequeues and returns the first character in the  instance variable.

Input Format

You do not need to read anything from stdin. The locked stub code in your editor reads a single line containing string . It then calls the methods specified above to pass each character to your instance variables.

Constraints

  •  is composed of lowercase English letters.

Output Format

You are not responsible for printing any output to stdout.
If your code is correctly written and  is a palindrome, the locked stub code will print ; otherwise, it will print 

Sample Input

racecar

Sample Output

The word, racecar, is a palindrome.
 

풀이

import sys

class Solution:
    # Write your code here
    stack = []
    queue = []
    def pushCharacter(self, character):
        self.stack.append(character)
    def popCharacter(self):
        return self.stack.pop()
    def enqueueCharacter(self, character):
        self.queue.append(character)
    def dequeueCharacter(self):
        char = self.queue[0]
        del self.queue[0]
        return char

# read the string s
s=input()
#Create the Solution class object
obj=Solution()   

l=len(s)
# push/enqueue all the characters of string s to stack
for i in range(l):
    obj.pushCharacter(s[i])
    obj.enqueueCharacter(s[i])
    
isPalindrome=True
'''
pop the top character from stack
dequeue the first character from queue
compare both the characters
''' 
for i in range(l // 2):
    if obj.popCharacter()!=obj.dequeueCharacter():
        isPalindrome=False
        break
#finally print whether string s is palindrome or not.
if isPalindrome:
    print("The word, "+s+", is a palindrome.")
else:
    print("The word, "+s+", is not a palindrome.")    

설명

문제를 한문장으로 정의하자면 "스택과 큐를 이용해 회문(palindrome)여부를 검사하기"이다. 회문은 단어나 문장을 뒤집어도 똑같은 단어나 문장이 되는 것들을 의미하는데(예: 기러기, 리효리, 소주만병만주소 등) 그 문제를 푸는 방법에 있어서 Stack과 Queue를 이용한다는 점이 굉장히 독특하고 또 기발해서 많이 기억이 남는다. 스택과 큐의 작동방식을 구분하고 만들어보는 데에 큰 도움이 될 것 같은 알고리즘 문제이다.

 알다시피 Stack은 LIFO형 자료구조이고 Queue는 FIFO형 자료구조인데 이게 어떻게 회문 검사에 쓰이는지 살펴보자. 예를 들어 "소주만병만주소"라는 문장이 있을 때 인덱스를 각 숫자에 맞게 1,2,3,4,5,6,7로 정의하자면 Stack은 7,6,5,4,3,2,1순서대로 출력 -> 고로 "소주만병만주소"가 그대로 출력된다. Queue는 반대로 1,2,3,4,5,6,7 순서로 출력되지만 각 인덱스에 저장돼있는 글자가 같으므로 똑같이 -> "소주만병만주소"가 출력되어 회문이라는 것이 증명된다.

두번째 예로 "소주만병좀주소"라는 문장을 대입해보자. Stack을 통해 "소주만병좀주소"를 출력하면 "소주좀병만주소"이 된다. Queue를 출력하면 "소주만병좀주소"가 된다. 그래서 이 문장은 회문이 아니게 되는 것이다.

 

Stack과 Queue, 그리고 회문이라는 개념을 혼합사용하면서 쉬우면서 많은 이해를 동반하는, 정말 좋은 문제이다.

Comments