[BOJ] [Python] 10845번 큐

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

10845번: 큐

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

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

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

 

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

풀이과정

총 3가지의 방법을 사용하면서 1번째는 실패한 것, 2번째와 3번째는 성공한 방법이다.

 

 1번째는 제목을 보자마자 Queue 클래스를 생각해서 봐로 구현을 해봤다. 하지만 index에서 오류가 발생했다. len을 사용해보기도 하고 queue.qsize()를 사용해봤지만 index자체에 접근을 할 수 없다고 한다. queue클래스는 index사용을 하지 않을 때 사용할 것을 알았다.

 

2번째는 list를 사용했다. list에서 추가와 삭제를 할 수 있는 method가 insert, append, pop 정도가 있다. 

append와 pop은 모두 list원소의 마지막만을 수정하는 method이다. 그래서 FIFO인 큐를 구현하기 위해서 insert를 사용한다.

첫번째 원소에 insert method를 사용해 삽입하고 제거할 때 pop method를 사용해서 큐를 구현했다.

 

3번째 collections.deque 를 사용해서 구현했다. deque는 list와 다르게 popleft, pop, appendleft, append 형식으로 왼쪽과 오른쪽을 method를 사용해 가독성이 좋게 구현할 수 있다. 이것을 통해서 2번째 방법보다 쉽고 가독성있게 구현했다.

 

2번째와 3번째 모두 왼쪽은 back, 오른쪽은 front이다.

 

 

 

코드

1번째  큐 클래스 사용

# silver 4
# 10845번, 큐

import queue, sys
N = int(input())
que = queue.Queue()

for i in range(N):
    # 명령어 입력
    cmd = sys.stdin.readline().rstrip().split()
    if cmd[0] == 'push':
        que.put(cmd[1])
    elif cmd[0] == 'pop':
        if not que.empty():
            print(que.get())
        else:
            print(-1)
    elif cmd[0] == 'size':
        print(que.qsize())
    elif cmd[0] == 'empty':
        if que.empty():
            print(1)
        else:
            print(0)
    elif cmd[0] == 'front':
        if que.empty():
            print(-1)
        else:
            # 인덱스 오류 발생
            print(que[len(que)-1])
    elif cmd[0] == 'back':
        if que.empty():
            print(-1)
        else:
            # 인덱스 오류 발생
            print(que[0])

큐 클래스는 index를 지원하지 않기 때문에 오류가 발생한다. 

 

2번째 list 사용

# silver 4
# 10845번, 큐
# list 사용

import sys

N = int(input())
que = list()

for i in range(N):
    # 명령어 입력
    cmd = sys.stdin.readline().rstrip().split()
    # 왼쪽이 뒤, 오른쪽이 앞
    if cmd[0] == 'push':
        que.insert(0, cmd[1])
    elif cmd[0] == 'pop':
        if len(que) == 0:
            print(-1)
        else:
            print(que.pop())
    elif cmd[0] == 'size':
        print(len(que))
    elif cmd[0] == 'empty':
        if len(que) == 0:
            print(1)
        else:
            print(0)
    elif cmd[0] == 'front':
        if len(que) == 0:
            print(-1)
        else:
            print(que[-1])
    elif cmd[0] == 'back':
        if len(que) == 0:
            print(-1)
        else:
            print(que[0])

 

3번째 collections.deque 사용

 

# silver 4
# 10845번, 큐
# collections.deque 사용

import sys, collections

N = int(input())
que = collections.deque()

for i in range(N):
    # 명령어 입력
    cmd = sys.stdin.readline().rstrip().split()
    # 왼쪽이 뒤, 오른쪽이 앞
    if cmd[0] == 'push':
        que.appendleft(cmd[1])
    elif cmd[0] == 'pop':
        if len(que) == 0:
            print(-1)
        else:
            print(que.pop())
    elif cmd[0] == 'size':
        print(len(que))
    elif cmd[0] == 'empty':
        if len(que) == 0:
            print(1)
        else:
            print(0)
    elif cmd[0] == 'front':
        if len(que) == 0:
            print(-1)
        else:
            print(que[-1])
    elif cmd[0] == 'back':
        if len(que) == 0:
            print(-1)
        else:
            print(que[0])

 

결론

밑이 list, 위가 collections.deque

 

성능차이는 크게 없는 것 같지만 가독성이 좋은 collections.deque를 사용해야겠다.

참고로 시간복잡도는 2번째 O(n) 3번째 O(1)이라고는 하는데 큰 차이를 모르겠다..