글 읽기 - deque 사용 여부가 시간 초과를 좌우하나요?

ssw02238 2년 전 0

import deque를 하지 않고 코드를 짰을 때 시간초과가 뜨는데

deque 를 쓰면 시간 초과가 안나네요 ㅠ

단순히 시간 초과 차이는 deque 유무인가요?

혹시 pop(0)과 deque.popleft() 사이에 시간 차이가 나나요?!

import sys
N = int(sys.stdin.readline())
queue = []

for i in range(N):
    command = sys.stdin.readline().split()

    if command[0] == 'push':
        queue.append(command[1])

    elif command[0] == 'pop':
        if queue:
            print(queue[0])
            queue.pop(0)
        else:
            print(-1)

    elif command[0] == 'size':
        print(len(queue))

    elif command[0] == 'empty':
        if queue:
            print(0)
        else:
            print(1)

    elif command[0] == 'front':
        if queue:
            print(queue[0])
        else:
            print(-1)
    else:
        if queue:
            print(queue[-1])
        else:
            print(-1)

dbshin59 2년 전 0

시간 차이가 있습니다.

처음에 [1, 2, 3] 이 있다고 합시다.

deque의 popleft()를 예로 들면,

1 2 3 -> 2 3 으로 맨 앞의 것이 사라집니다.

그러나, 일반적인 배열을 예로 들면,

1 2 3 -> 0 2 3 -> 2 0 3 -> 2 3 0 -> 2 3 으로 모든 원소를 다 일일히 옮기는 과정이 있어서 훨씬 오래 걸립니다.

ssw02238 2년 전 0

오 일반 배열을 삭제할 때 쓰는 pop(0) 은 저렇게 원소가 한칸씩 뒤로 밀려가는 시간이 발생한다고 보면 되나요?!

dbshin59 2년 전 0

그렇습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

deque 사용 여부가 시간 초과를 좌우하나요?

ssw02238 2년 전 0

dbshin59 2년 전 0

ssw02238 2년 전 0

dbshin59 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말