[실버 IV] 15828번. Router

 문제 

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

15828번: Router

 사용 언어 

Python3

 풀이 과정 

실버 IV인 만큼 문제를 읽고 한 줄씩 그대로 구현했더니 어렵진 않은 문제였다.

그런데 다른 스터디원들 이야기를 들어보니 50점을 맞은 분들이 꽤 있었고 시간초과가 이유일 것 같다는 추측이어서 

그 분들의 코드와 비교해보면 크게 아래 두 가지의 차이점이 있었다.

1. input() 대신 sys.stdin.readline() 사용
2. list, queue 자료형 대신 deque 사용

두 개가 속도가 빠르다고 공부했어서 귀찮아도 꼭 import해서 썼는데 이렇게 속도를 빡세게 보는 문제에서는 효과가 있었나보다.

어쨌든 한 번에 본 100점 ㅎㅎ

그리고 여담으로 solved 등급 확인을 직접 하지 않는 이상 몰랐는데 어느새  실버 III 레벨 이 되었다.

실력이 늘고 있나 의문이지만🤔 프로젝트도 끝났으니까 3차 플젝 전까지(다시 바빠지기 전까지)는 코딩 테스트 대비에 열중해야겠다. 이제 프로젝트도 해봤겠다 취업 지원서도 쓰고 싶은데 코딩 테스트 준비가 안돼 있는 걸 알아서 서류를 쓰고 싶지가 않은 상황... 정신차렷 면접이라도 보려면 코테가 제일 중요하다!!!😣

 제출 답안 

from sys import stdin
from collections import deque

input = stdin.readline
N = int(input()) # 라우터 크기, 라우터보다 더 많은 패킷이 들어오려고 하면 버려짐
# 양의 정수 : 입력 패킷 | 0 : 처리한 패킷 | -1 : 입력의 끝

packet = deque()
while True:
    tmp = int(input())
    if tmp == -1:
        break
    elif tmp == 0:
        packet.popleft()
    else:
        if len(packet) < N:
            packet.append(tmp)

if len(packet) == 0:
    print("empty")
else:
    print(*packet, sep = ' ')

 공부한 내용 

파이썬의 queue와 deque

파이썬에는 list, queue, deque 자료구조가 있는데 각각의 시간복잡도는 

list는 O(n)인 것에 비해 queue와 deque는 O(1)이다.

 

그렇다면 deque와 queue 중에선 뭐가 빠를까?

queue는 멀티 쓰레딩을 지원한다. 쉽게 말해서, 여러 스레드가 동시에 큐를 사용하더라도 문제가 없게끔 추가적인 작업을 수행한다는 것이다. 따라서 멀티쓰레딩 환경에서는 빛을 볼지는 몰라도 (문제 풀이에서는 불필요한) 동기화 과정을 거치기 때문에 기본적으론 deque가 빠르다.

심지어 deque는 리스트처럼 여러 가지 함수도 지원하기 때문에 웬만하면 deque를 사용하는 걸로!

출처: https://3d-storyge.tistory.com/8 | https://programming119.tistory.com/184