https://www.acmicpc.net/problem/18258
18258번: 큐 2
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
우선 이 문제는 큐 문제다.
큐의 특징을 잘 모르시면 문제를 해결하는데 어려움이 있을 수 있어, 간단하게 큐에 대해 설명하고 코드 설명하겠습니다.
큐란?
FIFO(First In First Out)의 특징을 가지고 있는 자료구조 중 하나입니다.
그림에서 볼수 있듯이 큐는 rear과 front를 사용해서 fifo의 특징을 유지합니다.
Item을 Enqueue(삽입)하게 되면 Front값을 1 더하고 Dequeue(삭제)하면 Rear의 값을 1 더합니다.
그러면 pop을 하지 않아도 Rear을 이용해서 삭제한 것과 같은 효과를 줄 수 있습니다.
중요!! 시간을 줄이는 큰 효과가 있습니다.
큐를 이해하는 매우 쉬운 방법은 군대를 상상하시면 됩니다.
먼저 입대한 선임병이 먼저 전역하듯이 큐는 먼저 들어간 데이터가 제일 먼저 나옵니다.
이제 이 개념을 문제에 대입해보겠습니다.
PushX == Enqueue, Pop == Dequeue로 이해하시면 문제를 더 쉽게 풀 수 있습니다.
1. PushX
|
1
2
3
|
if mission[0] == "push":
result_list.append(mission[1])
q_front += 1
|
cs |
result_list라는 리스트를 만든 뒤, push 뒤에 있는 값을 리스트에 넣습니다.
그 후, q_front에 1을 더합니다.
2. Pop
|
1
2
3
4
5
6
|
elif mission[0] == "pop":
if q_front > q_rear:
print(result_list[q_rear])
q_rear += 1
else:
print("-1")
|
cs |
q_front는 값을 넣을 때 더하는 변수고 q_rear은 값을 제거할 때 넣는 변수입니다.
문제에서 큐에 들어있는 정수가 없는 경우에는 -1을 출력하라고 했으니,
넣은 횟수보다 제거한 횟수가 비슷하거나 더 많으면 큐에 데이터가 없다고 이해하시면 됩니다.
그러므로 저는 (q_front > q_rear)을 데이터가 있는 조건으로 사용했습니다.
만약에 데이터가 있는 경우 데이터를 제거 한 뒤 q_rear에 1을 더했습니다.
3. Size
|
1
2
|
elif mission[0] == "size":
print(q_front - q_rear)
|
cs |
넣은 횟수에서 제거한 횟수를 빼면 현재 큐에 남아있는 원소의 개수를 알 수 있습니다.
4.Empty
|
1
2
3
4
5
|
elif mission[0] == "empty":
if q_front != q_rear:
print("0")
else:
print("1")
|
cs |
넣은 횟수와 제거한 횟수가 같으면 현재 큐에 값이 없는 것을 알 수 있습니다.
5. Front
|
1
2
3
4
5
|
elif mission[0] == "front":
if q_front != q_rear:
print(result_list[q_rear])
else:
print("-1")
|
cs |
Front는 맨 앞에 있는 원소를 출력하므로 q_rear을 출력했습니다.
값을 제거할 때마다 q_rear에 1을 더하므로 현재 맨 앞에 있는 원소는 q_rear가 가리키고 있습니다.
6. Back
|
1
2
3
4
5
|
elif mission[0] == "back":
if q_front != q_rear:
print(result_list[-1])
else:
print("-1")
|
cs |
Back은 맨 뒤에 있는 원소를 출력하므로 [-1]을 이용해서 출력했습니다.
정답코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
import sys
input = sys.stdin.readline
mission_num = int(input())
result_list = []
q_front = 0
q_rear = 0
for i in range(mission_num):
mission = input().split()
if mission[0] == "push":
result_list.append(mission[1])
q_front += 1
elif mission[0] == "front":
if q_front != q_rear:
print(result_list[q_rear])
else:
print("-1")
elif mission[0] == "back":
if q_front != q_rear:
print(result_list[-1])
else:
print("-1")
elif mission[0] == "pop":
if q_front > q_rear:
print(result_list[q_rear])
q_rear += 1
else:
print("-1")
elif mission[0] == "empty":
if q_front != q_rear:
print("0")
else:
print("1")
elif mission[0] == "size":
print(q_front - q_rear)
|
cs |