[BOJ] 15828번 Router

[BOJ] 15828번 Router 문제

큐(Queue)를 배우기 매우 좋은 문제다.

---

큐는 FIFO(First In First Out)의 형태를 가진 자료구조로, 처음 들어온 데이터가 처음으로 나간다. 이를 쉽게 이해하고 싶다면 빨대를 생각하면 된다.

빨대의 원리를 생각해보자. 우리가 빨대를 쪽 빨아대면 음료가 올라온다. 즉, 빨대랑 가장 가까운 음료부터 올라올 것이다. 이것이 바로 큐의 원리다.

하지만 이제 이 예시를 들어도 이해를 못 할 세대가 곧 오지 않을까 싶다

---

문제에서는 첫 숫자가 라우터 버퍼의 최대 개수를 뜻하고, -1이 들어올 때까지 이를 이용하여 연산한다. 0이 들어오면 패킷을 처리한 것으로 처리하고, 나머지가 들어오면 버퍼에 집어넣는데, 버퍼가 가득 차면 그 숫자를 못 넣는다. 또한 문제에서 라우터의 원리를 큐에 빗대어 설명했기 때문에 라우터 버퍼는 말 그대로 큐가 된다.

이를 이용해서 풀면 크게 어려운 문제는 되지 않는다.

import sys
from collections import deque

if __name__ == '__main__':
    N = int(sys.stdin.readline().rstrip())
    router = deque()

    while True:
        now_cmd = int(sys.stdin.readline().rstrip())
        if now_cmd == -1:
            break
        elif now_cmd == 0:
            router.popleft()
        else:
            if len(router) != N:
                router.append(now_cmd)

    if router:
        print(*router)
    else:
        print('empty')

 

코드에서 어려운 부분은 딱히 없다. 문제 지문에서 지시한 대로 처리하면 된다.

파이썬에서는 collection의 deque를 이용하면 쉽게 큐를 만들 수 있다. 이 deque는 데크라고 불리며, 기존의 큐에 양방향성이 추가된 것이다. 즉, 단방향성의 큐를 쓰는데에 문제가 전혀 없다.