[백준] 18158번 문제풀이

Rally·2024년 2월 22일

이슈

단순히 큐를 구현하는 문제지만, 백준 채점 결과 '시간초과' 발생하였다.

문제점 및 해결방안

1.1. 문제점(큐를 리스트로 구현)

class Queue:
    def __init__(self):
        self.items = []
    def push(self, x):
        self.items.append(x)
    def pop(self):
        return self.items.pop(0) if self.items else -1
	##### 이하 생략 #####

리스트의 기본 데이터 구조는 동적배열이다. 즉 인접한 메모리 위치에 저장된다는 의미이며, 새로운 item이 추가될때 메모리를 재할당한다. 그러므로 리스트의 앞단에서 데이터를 추가하거나 꺼내는 것은 성능이 좋지 않다. 다른 요소들을 모두 한칸씩 이동시켜야하기 때문이다( O(n) ).

1.2. 해결방안(collections.deque 사용)

파이썬의 주 데이터타입은 리스트인데 어떻게 해결해야하는 걸까? Python 공식 싸이트에서는 큐를 구현하려면 collections.deque 사용을 권장하고 있다. (https://docs.python.org/3/tutorial/datastructures.html#more-on-lists 참고)
deque는 double-ended-queue의 약어로 연결 리스트 구조이다. 양쪽 끝단에 있는 item을 처리할 시 O(1)를 나타낸다. 하지만 사이에 있는 값을 참조할 때 성능이 좋지 않다. (O(n) )

2.1. 문제점( input 함수의 성능)

N = int(input())
commands = [input() for _ in range(N)]

파이썬에서 대표적인 입력함수로 input이 있다. 다만 input은 파이썬 내장함수로 총 4단계의 절차를 가진다.

사용자로부터 입력을 받는다.

개행문자('\n')를 제거한다.

문자열로 변환한다.

결과를 반환한다.

입력되는 데이터가 많으면 현저히 낮은 성능을 보이게된다.

2.2. 해결방안(sys.stdin.readline 함수)

sys는 시스템 파라미터와 함수를 관리하는 모듈을 말한다. 그중 stdin은 표준입력 스트림으로 키보드와 같이 입력장치로부터 데이터를 받을 수 있다. readline는 2단계의 절차를 갖는다.

사용자 입력을 '\n'까지 입력받는다.

결과를 반환한다.
sys.stdin.readline은 개행문자를 필터링하지 않으므로 strip함수로 개행문자를 제거해줘야한다.

결론

양끝단에서 처리하는 작업에는 리스트보다 collections.deque 사용한다.
코딩문제에서 사용자로부터 입력값이 있으면 sys.stdin.readline()을 사용한다.

개선된 코드

import sys
from collections import deque

class Queue:
    def __init__(self):
        self.items = deque()

    def push(self, x):
        self.items.append(x)

    def pop(self):
        return self.items.popleft() if self.items else -1

    def size(self):
        return len(self.items)

    def empty(self):
        return 1 if not self.items else 0

    def front(self):
        return self.items[0] if self.items else -1

    def back(self):
        return self.items[-1] if self.items else -1
    
def process(commands):
    queue = Queue()
    output = []
    
    for command in commands:
        cmd = command.split()
        if cmd[0] == "push":
            queue.push(cmd[1])
        elif cmd[0] == "pop":
            output.append(queue.pop())
        elif cmd[0] == "size":
            output.append(queue.size())
        elif cmd[0] == "empty":
            output.append(queue.empty())
        elif cmd[0] == "front":
            output.append(queue.front())
        elif cmd[0] == "back":
            output.append(queue.back())
    return output

N = int(sys.stdin.readline().strip())
commands = [sys.stdin.readline().strip() for _ in range(N)]
results = process(commands)
print('\n'.join(map(str, results)))