[항해99] Queue

큐?

큐는 줄서기와 같다. 앞에 온 사람이 먼저 해결되는 방식이라고 생각하자.

영어로는 FIFO ( First In First Out ) 이라고 한다.

버스를 기다리는것은 큐와 같다.

큐 Structure

class Node:
    def __init__(self, item, next):
        self.item = item
        self.next = next


class Queue:
    def __init__(self):
        self.front = None

    def push(self, value):
        if not self.front:
            self.front = Node(value, None)
            return

        node = self.front
        while node.next:
            node = node.next
            node.next = Node(value, None)

    def pop(self):
        if not self.front:
            return None
        node = self.front
        self.front = self.front.next
        return node.item

    def is_empty(self):
        return self.front is None

 

큐는 스택과 달리 파이썬에서 기본으로 제공하지 않는다. 그래서 deque에서 큐 기능만 쓰면 큐를 쓸 수 있다.

근데 데큐가 기능이 더 많아서 데큐에서 다른 기능들도 사용하도록 하자. 

 

스택을 큐로 구현

https://leetcode.com/problems/implement-stack-using-queues/description/

Implement Stack using Queues - LeetCode

큐를 이용해서 스택을 구현하는 문제였다. 서로 방식이 완전히 반대인 자료구조라서 ( 스택은 FILO, 큐는 FIFO ) 새로운 걸 넣거나 제거하는 등의 행동을 할때 전부 다 빼서 다른 데다가 넣어놓고 행동을 한 뒤, 다시 돌려놓는 작업을 필요로 했다.

 

해결 코드

# https://leetcode.com/problems/implement-stack-using-queues/description/
from collections import deque

class MyStack:

    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

    def push(self, x: int) -> None:
        self.q1.append(x)

    def pop(self) -> int:
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())

        ret = self.q1.popleft()

        self.q1, self.q2 = self.q2, self.q1

        return ret

    def top(self) -> int:
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        ret = self.q1.popleft()
        self.q2.append(ret)

        self.q1, self.q2 = self.q2, self.q1

        return ret

    def empty(self) -> bool:
        return len(self.q1) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

큐를 스택으로 구현

https://leetcode.com/problems/implement-queue-using-stacks/

Implement Queue using Stacks - LeetCode

class MyQueue:

    def __init__(self):
        self.s1 = []
        self.s2 = []

    def push(self, x: int) -> None:

        while len(self.s1) > 0:
            self.s2.append(self.s1.pop())
        self.s1.append(x)
        # 순서가 뒤집혀있으니까 다시 넣어줘야함.
        while len(self.s2) > 0:
            self.s1.append(self.s2.pop())
        # print("s1: ", self.s1)
        # print("s2: ", self.s2)


    def pop(self) -> int:
        ret = self.s1.pop()
        
        return ret

    def peek(self) -> int:
        ret = self.s1.pop()
        self.s1.append(ret)
        return ret


    def empty(self) -> bool:
        return len(self.s1) == 0


# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

원형 큐 구현

https://leetcode.com/problems/design-circular-queue/description/

Design Circular Queue - LeetCode

기존 큐는 직선으로 이루어져, 앞으로 자료가 나가고 뒤로 자료가 들어오는 구조였는데, 원형큐는 원형으로 되어있어 자료를 넣었다가 빼면 다시 뺀 곳에 다시 새로운 자료를 넣는 방식으로 되어있다. 

이런 식으로 생겼다고 생각하면 된다.

여기서 포인트는 큐를 삭제할 때 그냥 head를 나타내는 인덱스를 한칸 뒤로 밀어버린다면 ( 그러니까, 2가 헤드가 되도록 만든다면 ) 간편하게 삭제 연산을 할 수 있다. ( 개수를 나타내는 카운터 값도 하나 줄여야 해요. )

class MyCircularQueue:

    def __init__(self, k: int):
        self.queue = [0] * k
        self.cnt = 0
        self.headidx = 0
        self.size = k

    def enQueue(self, value: int) -> bool:
        if self.isFull():
            return False
        self.queue[(self.headidx + self.cnt) % self.size] = value
        self.cnt += 1
        return True


    def deQueue(self) -> bool:
        if self.isEmpty():
            return False
        
        self.headidx = (self.headidx + 1) % self.size
        self.cnt -= 1
        return True

    def Front(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[self.headidx]

    def Rear(self) -> int:
        if self.isEmpty():
            return -1
        return self.queue[(self.headidx + self.cnt - 1) % self.size]

    def isEmpty(self) -> bool:
        return self.cnt == 0

    def isFull(self) -> bool:
        return self.cnt == self.size


# Your MyCircularQueue object will be instantiated and called as such:
# obj = MyCircularQueue(k)
# param_1 = obj.enQueue(value)
# param_2 = obj.deQueue()
# param_3 = obj.Front()
# param_4 = obj.Rear()
# param_5 = obj.isEmpty()
# param_6 = obj.isFull()

카드2

https://www.acmicpc.net/problem/2164

2164번: 카드2

문제에서 제시된 대로 구현만 하면 해결되는 간단한 문제였다.

 

해결 코드

from collections import deque


def test_problem_queue(num):
    deq = deque([i for i in range(1, num + 1)])
    while len(deq) > 1:
        deq.popleft()
        deq.append(deq.popleft())

    return deq.popleft()


i = int(input())
print(test_problem_queue(i))

 

프린터 큐

https://www.acmicpc.net/problem/1966

1966번: 프린터 큐

처음 문제를 봤을 때 어..? 우선순위큐로 풀 수 있지 않을까? 라는 생각으로 접근했는데, 답이 틀렸다고 해서 뭐지... 하고 엄청 고민을 많이 했다.

문제코드

from queue import PriorityQueue

numTestCases = int(input())
for _ in range(numTestCases):
    N, M = map(int, input().split())
    lst = list(map(int, input().split()))
    que = PriorityQueue()
    idx = 0
    for i, val in enumerate(lst):
        que.put((i, val))

    while idx < M:
        idx += 1
        que.get()[1]
    print(que.get())

인덱스와 우선순위 점수를 담은 튜플을 우선순위 큐에 넣고, 우선순위가 높은 자료부터 que.get()[1] 을 이용해서 뽑아냈다.

해결

문제 조건을 제대로 안 읽었었다. 

 

문제 2번 조건에 : 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다

라는 말이 있었는데 이 조건이 문제를 풀 때 꼭 필요하고, Queue를 이렇게 활용해라! 라는 팁까지 있었는데 문제를 더 잘 읽어야 겠다.. .. 

 

그리고 큐에 어떤 값을 넣을 지도 잘 생각해서 인덱스를 넣을 것인지, 우선순위 점수를 넣을 것인지를 잘 판단해서 풀어야 겠다. 

해결 코드

from collections import deque

numTestCases = int(input())
for _ in range(numTestCases):
    n, m = map(int, input().split())
    priority_queue = deque(map(int, input().split()))
    cnt = 0

    while True:
        max_prior = max(priority_queue)
        curr = priority_queue.popleft()
        m -= 1

        if max_prior == curr:
            cnt += 1
            if m < 0:
                print(cnt)
                break

        else:
            priority_queue.append(curr)
            if m < 0: # 제일 앞에서 뽑힌 경우
                m = len(priority_queue) - 1