HackerRank Queues: A Tale of Two Stacks


입력

  • q, 쿼리의 숫자
  • 쿼리 타입, 1만 뒤에 추가적인 값이 따라온다.

쿼리 타입

  • 1: x를 enqueue 한다.
  • 2: dequeue
  • 3: print 1개만

이 challenge에서는 반드시 queue를 두개의 stack을 이용해서 구현하라고 한다.
이게 front에서 팝이랑 삽입이 모두 이뤄져야 하기 때문에 통상의queue랑은 다르다.

List를 이용한 직접 작성한 Queue

class MyQueue(object):
    def __init__(self):
        self.q = [] 
        self.right = 0
        
    def peek(self):
        if self.q:
            return self.q[0]
        
    def pop(self):
        if self.q:
            self.q.pop()
            self.right -= 1
                
    def put(self, value):        
        self.q.insert(self.right,value)
        self.right += 1

새로운 queue

Class Queue:
    def __init__(self):
        self.items = []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        self.items.pop()

    def print_queue(self):
        print(self.items)

    def is_empty(self):
        return self.items == []

    def size(self):
        return len(self.items)

어려운 Test Case

10
1 76
1 33
2
1 23
1 97
1 21
3
3
1 74
3

정답

33
33
33

정답

class MyQueue(object):
    def __init__(self):
        self.old_to_new = []
        self.new_to_old = []
   
    def peek(self):
        if not self.new_to_old:
            while self.old_to_new:
                self.new_to_old.append(self.old_to_new.pop())
        val = self.new_to_old.pop()
        self.new_to_old.append(val)
        return val
       
    def pop(self):
        if not self.new_to_old:
            while self.old_to_new:
                self.new_to_old.append(self.old_to_new.pop())
        return self.new_to_old.pop()
       
    def put(self, value):
        self.old_to_new.append(value)


        
queue = MyQueue()
t = int(input())
for line in range(t):
    values = map(int, input().split())
    values = list(values)
    if values[0] == 1:
        queue.put(values[1])        
    elif values[0] == 2:
        queue.pop()
    else:
        print(queue.peek())


'Computer Science > Coding Interview' 카테고리의 다른 글

HackerRank- Trees: Is This a Binary Search Tree  (0) 2017.07.31
Binary Search Tree  (0) 2017.07.31
Stacks: Balanced Brackets  (0) 2017.07.30
HackerRank Data Structure  (0) 2017.07.30
HackerRank MergeSort Counting Inversions  (0) 2017.07.29

+ Recent posts