[백준] 15828번 Router

출처: [백준] 17952번 과제는 끝나지 않아!

---

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	512 MB	746	440	375	61.275%

---

문제

인터넷을 사용하기 위해서는 컴퓨터에 인터넷 회선을 연결하거나 Wi-Fi를 연결해야 한다. 이렇게 연결된 네트워크를 통해 컴퓨터에는 통신이 가능하다. 마음에 드는 노래나 동영상이 있는 곳에 파일을 전송해달라는 요청을 보내고 파일을 받는 식으로 말이다.

우리가 보낸 요청은 어떻게 목적지까지 도달하는 것일까? 컴퓨터에서는 패킷이라고 하는 형태로 정보를 주고 받는다. 네트워크의 유저들은 1:1로 연결되어 있지 않으므로, 일반적으로 패킷은 라우터라는 장비를 여러 번 거친다. 그러면 라우터에서는 패킷을 다른 라우터로 보내거나, 만약 목적지와 직접적으로 연결되어 있다면 그곳으로 보낼 수도 있다. 즉, 택배 회사의 물류 센터와 비슷한 역할을 한다고 보면 된다.

그림1. 네트워크에 존재하는 라우터들의 구성 예시

라우터 내부를 들여다보면 처리해야 할 패킷을 임시적으로 보관하기 위한 버퍼가 존재한다. 이 버퍼에는 라우터에 입력으로 들어온 패킷들이 순서대로 위치하고, 라우터에서는 먼저 온 패킷부터 하나씩 처리한 후 버퍼에서 제거한다. 만약 라우터가 패킷을 처리하는 속도보다 패킷이 들어오는 속도가 더 빠를경우 버퍼가 꽉 차거나 넘쳐버릴 것이다. 그렇게 되면 버퍼에 공간이 생길 때까지 입력받는 패킷은 모두 버려진다.

통신의 원리를 배웠으니까 간단하게 라우터의 작동 원리를 구현해보자. 물론 하나의 라우터만 존재한다고 가정하며, 우리가 다룰 부분은 라우터의 입출력이 주어졌을 때 버퍼의 상태가 어떻게 변하는가이다. 그러니까 라우터가 패킷을 구체적으로 어떤 방식으로 처리하고, 어디로 보내고 이런 것들은 생각하지 말자.

---

입력

첫 줄에는 라우터 내부에 존재하는 버퍼의 크기를 나타내는 자연수 N이 주어진다.

둘째 줄부터 한 줄에 하나씩 라우터가 처리해야 할 정보가 주어진다. 모든 정보는 발생한 시간순으로 주어졌다고 가정한다. 양의 정수는 해당하는 번호의 패킷이 입력으로 들어왔다는 것을 의미하고, 0은 라우터가 패킷 하나를 처리했다는 것을 의미한다. 이때, 버퍼가 비어있을때는 0이 입력으로 들어오지 않는다. -1은 입력의 끝을 나타낸다.

---

출력

라우터에 남아있는 패킷을 앞에서부터 순서대로 공백으로 구분해서 출력하면 된다. 만약 비어있을 경우 empty라고 출력한다.

---

Small (50점)

• 1 ≤ N ≤ 100,000
• 라우터가 처리해야 할 정보의 수는 N보다 작거나 같다.

Large(50점)

• 1 ≤ N ≤ 100,000
• 1 ≤ N ≤ 100,000

---

예제 입력 1

5
1
2
0
3
4
0
5
6
0
0
-1

예제 출력 1

5 6

예제 입력 2

1
1
2
3
4
5
6
7
-1

예제 출력 2

1

예제 입력 3

1
1
2
0
3
4
0
5
6
0
7
0
-1

예제 출력 3

empty

---

출처

• University > 아주대학교 > 2018 Ajou Programming Contest: Division 2 B번
  • 문제를 만든 사람: luke0201

---

알고리즘 분류

• 자료 구조
• 큐

---

소스코드

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
buffer = deque()
full = 0
while True:
    packet = int(input())

    if packet == -1:
        break
    elif packet == 0:
        buffer.popleft()
        full -= 1
    else:
        if full >= N:
            continue
        else:
            buffer.append(packet)
            full += 1

if buffer:
    print(*buffer)
else:
    print("empty")