[알고리즘](Python) 백준 10845번 - 큐

문제

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

10845번: 큐

주제	큐
시간 / 메모리 제한	0.5 초 / 256 MB
정답 비율	48.970%

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

명령은 총 여섯 가지이다.

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

입력

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

출력

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

- 예제 입력 1

15
push 1
push 2
front
back
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
front

- 예제 출력 1

1
2
2
0
1
2
-1
0
1
-1
0
3

큐 개념

 

큐(queue)는 선입선출을 뜻하는 FIFO(First In First Out) 구조이다.

먼저 들어온 데이터가 먼저 나가며, 새롭게 추가된 데이터는 큐의 맨 뒤에 추가된다.

큐의 ADT는 다음과 같다.

### 스택의 ADT ###
# Object
    : FIFO 객체
# Operation
    1. is_empty() -> Boolean
        : 큐가 비어 있으면 True, 아니면 False 반환
    2. is_full() -> Boolean
        : 큐가 가득 찼으면 True, 아니면 False 반환
    3. enqueue(data)
        : 큐의 맨 뒤에 데이터 삽입
    4. dequeue() -> element
        : 큐의 맨 처음 데이터를 삭제하면서 반환
    5. peek() -> element
        : 큐의 맨 처음 데이터를 삭제하지 않고 반환만 함

큐는 단순히 선형으로도 구성할 수 있지만 원형으로 구성할 수도 있다.

밑에 문제는 선형 큐로 구현하여 풀었다.

정답 풀이

시간 초과된 풀이

input()을 사용하니 시간 초과가 발생하였다.

class Queue:

    def __init__(self):
        self.container = list()
        self.size = 0

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

    def push(self, data):
        self.container.append(data)
        self.size += 1

    def pop(self):
        if self.size < 1:
            return -1
        self.size -= 1
        return self.container.pop(0)

    def front(self):
        if self.size < 1:
            return -1
        return self.container[0]

    def back(self):
        if self.size < 1:
            return -1
        return self.container[self.size - 1]


import sys

N = int(sys.stdin.readline())
queue = Queue()

for i in range(N):
    line = input().split()

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

    elif line[0] == 'pop':
        print(queue.pop())

    elif line[0] == 'size':
        print(queue.size)

    elif line[0] == 'empty':
        print(queue.empty())

    elif line[0] == 'front':
        print(queue.front())

    elif line[0] == 'back':
        print(queue.back())

정답 풀이

input()을 sys.stdin.readline()로 대체하여 작성했더니 통과했다.

class Queue:

    def __init__(self):
        self.container = list()
        self.size = 0

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

    def push(self, data):
        self.container.append(data)
        self.size += 1

    def pop(self):
        if self.size < 1:
            return -1
        self.size -= 1
        return self.container.pop(0)

    def front(self):
        if self.size < 1:
            return -1
        return self.container[0]

    def back(self):
        if self.size < 1:
            return -1
        return self.container[self.size - 1]


import sys

N = int(sys.stdin.readline())
queue = Queue()

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

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

    elif line[0] == 'pop':
        print(queue.pop())

    elif line[0] == 'size':
        print(queue.size)

    elif line[0] == 'empty':
        print(queue.empty())

    elif line[0] == 'front':
        print(queue.front())

    elif line[0] == 'back':
        print(queue.back())