[ 백준 15828 ] Router ( feat. 파이썬 )

[ 문제 분류 ]

- Queue

 

[ 백준 문제 링크 ]

- https://www.acmicpc.net/problem/15828

15828번: Router

 

[ 라우터 문제 요약 ]

- 라우터에는 패킷이 순서대로 들어옴 ( 먼저 들어온 패킷이 우선 처리 됨 -> 선입선출 구조 )

- 양의 정수 값을 가진 패킷이 입력으로 들어올 수 있고, 0은 패킷 하나를 처리한다는 의미

- 라우터의 버퍼가 꽉 찬 경우 입력 값이 들어와도 받을 수 없음. 버퍼의 공간이 생기고 나서 부터 들어온 값만 받을 수 있음

- -1 입력 시 패킷이 더 이상 오지 않음을 의미하고 종료 / 남아있는 패킷 출력하기

 

 

[ 풀이 코드 예시 ]

from collections import deque
import sys

deq = deque()
q_size = int(sys.stdin.readline())
while(1):
    num = int(sys.stdin.readline())
    if num == -1:
        if deq:
            print(*deq)
            break
        else :
            print('empty')
        break    
    else:
        if num == 0:
            deq.popleft()
        else:
            if len(deq) < q_size:
                deq.append(num)

- 선입선출 구조이므로 큐를 사용 

- input( ) 함수를 사용할 수도 있지만 속도/성능을 위해 sys.stdin 사용

- 먼저 들어온 패킷을 먼저 제거하기 위해 popleft( ) 사용

- 버퍼 사이즈 체크를 통해 버퍼가 꽉 차있지 않을 경우만 append

 

 

[ 관련 내용 ] 

1. 큐를 리스트가 아닌 deque를 통해 구현한 이유

- list 보다 deque의 속도가 훨씬 빠르기 때문!

- list는 O(n)의 속도를 , deque는 O(1)의 속도를 가짐

 

 

[ 관련 파이썬 함수 ]

1. sys.stdin.readline()

- 한 두줄 입력 받는 문제들과 다르게, 반복문으로 여러 줄을 받을 때는 input()으로 입력 받으면 시간 초과가 날 수 있음.
- 한줄 단위로 입력 받기 떄문에 개행 문자가 같이 입력 받아짐. ( 정수 값으로 사용하려면 형변환을 거쳐야! )

[ 예시 ]
1. 정해진 개수의 정수를 한줄에 입력 받을 때

import sys
a,b,c = map(int, sys.stdin.readline().split())​

2. 임의의 개수의 정수를 한번에 입력 받아 리스트에 저장할 때

import sys
nums = list(map(int, sys.stdin.readline().split()))​

3. 임의의 개수의 정수를 n 줄 입력받아 2차원 리스트에 저장할 때

import sys
nums= []
n = int(sys.stdin.readline())
for i in range(n):
	data.append(list(map(int,sys.stdin.readline().split())))

 

---