[백준/Python] 18258 큐2

문제: https://www.acmicpc.net/problem/18258

 

 

사용 알고리즘: 큐

 

 

입력

• 첫째 줄에 주어지는 명령의 수 N (1 <= N <= 2,000,000)
• 둘째 줄부터 N 개의 줄에는 명령이 하나씩 주어짐. 주어지는 정수는 1 이상 100,000 이하이다. 

 

명령은 총 6가지

• push X: 정수 X를 큐에 넣는 연산
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력, 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력
• size: 큐에 들어있는 정수의 개수를 출력
• empty: 큐가 비어있으면 1, 아니면 0을 출력
• front: 큐의 가장 앞에 있는 정수를 출력, 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력
• back: 큐의 가장 뒤에 있는 정수를 출력, 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력

 

일단 시간 초과로 한 번 틀렸는데, 틀린 코드부터 살펴보자. (시간 초과가 젤 열받음)

 

틀린 코드

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())

Q = deque()

for i in range(N):
    command = input().rstrip()
    num = 0
    try:
        command, num = command.split(' ')
    except ValueError:
        pass
    if command == 'push':
        Q.append(int(num))
    elif command == 'pop':
        if len(Q) == 0:
            print(-1)
        else:
            print(Q.popleft())
    elif command == 'front':
        if len(Q) == 0:
            print(-1)
        else:
            print(Q[0])
    elif command == 'back':
        if len(Q) == 0:
            print(-1)
        else:
            print(Q[-1])
    elif command == 'size':
        print(len(Q))
    elif command == 'empty':
        if len(Q) == 0:
            print(1)
        else:
            print(0)

 

뜬금없이 시간초과길래 대체 어디서 틀렸을까 하고 코드를 보던 중, 의심스러운 try-except 구문

다른 곳에서 시간 잡아먹을 일이 없는 것 같아서 try-except 구문을 없애고 다른 방식으로 코드를 짰더니 시간 초과 없이 통과됐다. 

역시 try-except 구문이 문제인건 맞는데, 왜 문제일까 정확히 알고 싶어서 지피티에게 물어봤다.

 

일단 이 부분이 문제가 맞고, 이 부분에는 2가지 문제점이 있었다. 

try:
    command, num = command.split(' ')
except ValueError:
    pass

 

 

문제점1 - 불필요한 예외처리

 

문자열이 항상 두 부분(명령과 숫자)으로 나뉘는 것이 아님. push 명령어의 경우에만 두 부분으로 나뉨.

근데 for 문을 돌면서 매번 불필요한 예외 처리 과정을 거쳐야함.

-> 명령어의 개수 N 의 최대값은 2백만, N 값이 커질수록 어마무시하게 큰 시간적 비용이 될 것!

 

문제점2 - split 의 반복 사용

 

문제점1에서 파생된 문제인데, 매번 try-except 처리를 하기 때문에 split 이 필요하지 않은 명령어에도 계속 split 을 사용함.

-> 결국 문제점1과 동일하게 N 값이 커질수록 시간적 비용이 매우 커질 것!

 

(다음에는 이런 실수하지 말아야지)

 

 

그럼 이제 통과된 코드를 살펴보자. 

 

일단 try-except 구문을 없앴다.

push 는 예외적인 경우이기 때문에 else 문으로 처리를 해주었다. 

위에서 다 필터링 되고 내려온 명령어는 무조건 push 이기 때문에 push 문자열과 공백 한자리를 제외하고 5번 인덱스부터 숫자로 타입을 변환해서 push 해주는 방식으로 코드를 짰다. 

 

전체 코드

import sys
from collections import deque
input = sys.stdin.readline

N = int(input())

Q = deque()

for i in range(N):
    command = input().rstrip()
    num = 0
    if command == 'pop':
        if len(Q) == 0:
            print(-1)
        else:
            print(Q.popleft())
    elif command == 'front':
        if len(Q) == 0:
            print(-1)
        else:
            print(Q[0])
    elif command == 'back':
        if len(Q) == 0:
            print(-1)
        else:
            print(Q[-1])
    elif command == 'size':
        print(len(Q))
    elif command == 'empty':
        if len(Q) == 0:
            print(1)
        else:
            print(0)
    else:
        Q.append(int(command[5:]))

 

 

 

시간 복잡도

 

이 코드의 시간 복잡도는 O(n) 이다. 

 

각 명령의 실행

• push: O(1)
• pop: O(1)
• size: O(1)
• empty: O(1)
• front: O(1)
• back: O(1)

참고로 리스트로 큐 자료구조를 구현해본 사람이라면 pop 은 O(n) 아닌가? 라는 의문이 들 수도 있다.

리스트로 큐 자료구조를 구현했다면 그게 맞지만 나는 이미 파이썬에 구현되어 있는 deque 를 써서 큐처럼 사용했기 때문에 O(1) 시간이다. deque 는 양쪽 끝에서 모두 삽입과 삭제 연산이 가능하며 O(1) 의 시간 복잡도를 가진다. 

( 그리고 이 문제에서 리스트로 큐를 구현해서 사용했다면 시간초과가 났을 것이다 )

 

그리고 또 의문이 드는 부분이 있을 것이다. 문자열 슬라이싱의 시간복잡도는 O(k) 시간이다. 

슬라이싱은 문자열의 일부를 복사해서 새 문자열을 생성하는 작업이기 때문에 슬라이스의 길이에 따라 시간이 선형적으로 증가한다.

여기서는 push 와 공백 한개 해서 총 5개의 글자만 슬라이싱하기 때문에 성능에 큰 영향을 미치지 않는다. (고한다 지피티가)

 

아무튼 그래서 for 문을 도는 데 걸리는 시간만 생각하면 되기 때문에 총 시간 복잡도는 O(n) 이다.