[WEEK 02] 알고리즘 - 큐 문제풀이

18258. 큐 2

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

큐의 기능들을 이용해 주어진 명령들을 실행하는 기초적인 문제.

import sys
from collections import deque

sys.stdin = open("4-1_18258.txt", "r")
input = sys.stdin.readline

queue = deque()

N = int(input())

arr = [input().split('\n')[0] for i in range(N)]

for str in arr:
    if str.split()[0] == 'push':
        queue.append(str.split()[1])
    elif str == 'pop':
        if len(queue) != False:
            print(queue[0])
            queue.popleft()
        else:
            print(-1)
    elif str == 'size':
        print(len(queue))
    elif str == 'empty':
        if len(queue) != False:
            print(0)
        else:
            print(1)
    elif str == 'front':
        if len(queue) != False:
            print(queue[0])
        else:
            print(-1)
    elif str == 'back':
        if len(queue) != False:
            print(queue[-1])
        else:
            print(-1)

---

2164. 카드2

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

카드에 적힌 숫자 순서대로 쌓은 카드를 한장 씩 버리고 밑으로 옮기는 과정을 반복하여 남은 마지막 카드의 숫자를 구하는 문제. 큐의 popleft()와 append() 기능을 반복적으로 수행하는 while문을 사용하여 답을 구할 수 있었다.

import sys
from collections import deque

input = sys.stdin.readline

N = int(input())

queue = deque()

for i in range(1, N + 1):
    queue.append(i)

while len(queue) > 1:
    queue.popleft()
    queue.append(queue[0])
    queue.popleft()

print(int(queue[0]))

---

11866. 요세푸스 문제 0

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

import sys
from collections import deque

input = sys.stdin.readline

N, K = map(int, input().split())

queue = deque([i for i in range(1, N + 1)])

answer = []
cnt = 0

while len(queue) >= 1:
    cnt += 1
    if cnt % K == 0:
        queue.rotate(-(K - 1))
        answer.append(queue[0])
        queue.popleft()

print('<', end='')

for j in range(len(answer)):
    if j != len(answer) - 1:
        print("%d, " %answer[j], end='')
    else:
        print("%d>" %answer[j])

큐라는 개념을 자유롭게 사용하기 위해서는 deque의 rotate() 기능을 보다 정확하게 이해하는 것이 필요할 것 같다. 문제에서 요구하는 형태에 맞게 답을 출력하는 것 또한 어려웠다.