[자료구조] [BJ10845] 큐

코드 플러스

🚩 문제 설명

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

10845번: 큐

BJ10845

 

⏱️ 시간 복잡도
▪️ 명령의 수가 N개 주어진다.
▪️ 명령어의 갯수는 총 6가지 이다.
▪️ 데이터에 대한 접근은 O(N)이라고 할 수 있다.
▪️ 데이터 접근은 back이나 front
▪️ 따라서 시간복잡도는 대략적으로 O(2 x N x N)이라고 할 수 있다.
▪️ 2 x 10^10 / 10^8 = 2 x 10^2 = 200s
▪️ 이러면 시간초과가 나온다. 그러니까 데이터 접근이 빠른 방법을 써야한다.
▪️ deque를 쓰면 무작위 접근으로 O(N)에 해당한다.
▪️ Queue를 쓰면 데이터 추가/삭제는 O(1), 데이터 접근은 O(N)에 해당한다.

◾ 주어지는 명령어에 따라서 값을 출력하는 문제

◾ 명령어

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

 

➕

📚Python에서 Queue 사용하기
1. List 자료구조 사용
2. Deque 자료구조 사용
3. Queue 자료구조 사용

 

✔️ List

list() 사용

◾ 리스트 요소 추가 : append(), insert()

queue = [1, 2, 3]

# 리스트 요소 추가
queue.append(5) 
>>> [1, 2, 3, 5]

queue = [1, 2, 3]

# 리스트 요소 추가
queue.insert(0, 5) 
>>> [5, 1, 2, 3]

 

◾ 리스트 요소 삭제 : pop()

queue = [1, 2, 3]

# 리스트 요소 삭제 : back 값 삭제
queue.pop()
>>> [1, 2]

queue = [1, 2, 3]

# 리스트 요소 삭제 : front 값 삭제
queue.pop(0)
>>> [2, 3]

 

◾ front 값 구하기

queue = [1, 2, 3]

# front 값
print(queue[0])
>>> 1

 

◾ back 값 구하기

queue = [1, 2, 3]

# back 값
print(queue[-1])
print(queue[len(queue) - 1])
>>> 3

 

◾ 리스트 비어있는지 아닌지 확인하기

queue = [1, 2, 3]

# 리스트 비어있는지 아닌지
print(True if len(queue) == 0 else False)
>>> False

 

◾ 리스트 크기 구하기

queue = [1, 2, 3]

# 리스트 비어있는지 아닌지
print(len(queue))
>>> 3

 

✔️ Deque

from collections import deque

◾ back에 요소 추가 : append()

from collections import deque

queue = deque([1, 2, 3])

# 리스트 추가하기 : back
queue.append(4)
print(queue)
# deque([1, 2, 3, 4])

 

◾ front에 요소 추가 : appendleft()

from collections import deque

queue = deque([1, 2, 3])

# 리스트 추가하기 : front
queue.appendleft(4)
print(queue)
# deque([4, 1, 2, 3])

 

◾ back에 요소 삭제 : pop()

from collections import deque

queue = deque([1, 2, 3])

# 리스트 추가하기 : back
queue.pop()
print(queue)
# deque([1, 2])

 

◾ front에 요소 삭제 : popleft()

from collections import deque

queue = deque([1, 2, 3])

# 리스트 추가하기 : back
queue.popleft()
print(queue)
# deque([2, 3])

 

✔️ Queue

from queue import Queue

◾ 요소 추가 및 삭제

from queue import Queue

queue = Queue()

# 요소 추가
queue.put(1)
queue.put(2)
queue.put(3)

# 요소 삭제, 꺼내기
print(queue.get()) # 1
print(queue.get()) # 2
print(queue.get()) # 3

 

◾ 큐 사이즈 확인

from queue import Queue

queue = Queue()

# 요소 추가
queue.put(1)
queue.put(2)
queue.put(3)

# 사이즈 확인
print(queue.qsize())
# 3

 

 

 

---

 

 

 

✅ 입출력

1) N : 주어지는 명령의 수
2) 둘째 줄 부터는 명령어가 하나씩 주어진다.
return ➡️ 명령어에 따른 결과를 출력한다.

✔️ 예제 1

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

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

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys
from collections import deque

input = sys.stdin.readline
que = deque()  # queue
N = int(input())  # 명령어 수

for n in range(N):
    com = input().split()

    if com[0] == 'push':
        que.append(com[1])

    elif com[0] == 'back':
        if que:
            print(que[-1])
        else:
            print(-1)

    elif com[0] == 'front':
        if que:
            print(que[0])
        else:
            print(-1)

    elif com[0] == 'size':
        print(len(que))

    elif com[0] == 'empty':
        if not que:
            print(1)
        else:
            print(0)

    elif com[0] == 'pop':
        if not que:
            print(-1)
        else:
            print(que.popleft())

💬 Point

➡️  deque 사용
➡️  deque의 popleft()를 사용하면 front 값을 뽑아낼 수 있다.

◾ input() 쓰니까 시간초과 나오던게

◾ import sys 하고 input = sys.stdin.readline 하니까 바로 제출된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 코드플러스 큐 파이썬

# 백준 18045 큐 파이썬

---