[Algorithms] 스택,큐,해쉬,힙-공주 규하기(큐)

 

 

• 파이썬에서 제공하는 deque 자료구조를 가지고 원형 queue를 구현 해보는 문제

 

 

• 처음에는 파이썬에서 제공하는 deque을 이용하지 않고 포인터를 쓴다는 개념으로 접근해서 풀이했다

import sys
 
sys.stdin = open("input", "rt")
n, k = map(int, input().split())
 
queue = list(range(1, n+1))
pointer=0
cnt=0
while len(queue) > 1:
    if pointer==len(queue):
        pointer=0
    if cnt==k-1:
        queue.pop(pointer)
        cnt=0
        continue
    pointer+=1
    cnt+=1
 
print(queue.pop())
 
 

• deque을 사용한 풀이

import sys
from collections import deque
 
# sys.stdin = open("input", "rt")
n, k = map(int, input().split())
 
deq = list(range(1, n+1))
deq = deque(deq)
 
while deq:
    for _ in range(k-1):
        temp=deq.popleft()
        deq.append(temp)
    deq.popleft()
    if len(deq)==1:
        print(deq.popleft())