.PNG)
공주 구하기(큐 자료구조로 해결)
정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.
정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은
다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.
왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N
번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시
계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그
왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시
1부터 시작하여 번호를 외친다.
이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.
1
8 2
7 3
6
5
4
예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자. 처음에는 3번 왕자가 3
을 외쳐 제외된다. 이어 6, 1, 5, 2, 8, 4번 왕자가 차례대로 제외되고 마지막까지 남게 된 7
번 왕자에게 공주를 구하러갑니다.
N과 K가 주어질 때 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.
▣ 입력설명
첫 줄에 자연수 N(5<=N<=1,000)과 K(2<=K<=9)가 주어진다.
▣ 출력설명
첫 줄에 마지막 남은 왕자의 번호를 출력합니다.
▣ 입력예제 1
8 3
▣ 출력예제
<내 풀이>
from collections import deque
n, m = map(int, input().split())
que=deque()
for i in range(n) :
que.append(i+1)
cnt=0
while len(que) >1:
que.append(que.popleft())
cnt+=1
if cnt==m:
que.pop()
cnt=0
print(que[0])
<풀이>
from collections import deque
n, m = map(int, input().split())
dq=list(range(1,n+1))
dq=deque(dq)
while dq :
for _ in range(m-1) : #m가 3이면 range(m-1)은 range(2), 이는 0,1 까지만 도는 것
cur=dq.popleft()
dq.append(cur)
dq.popleft()
if len(dq) == 1 :
print(dq[0])
dq.popleft()
<반성점>
- 저번에 배운 1부터 n까지의 리스트 구하는 방식 까먹음
=> dq=list(range(1,n+1))
이렇게 구하면 됨
<배운 점>
-
큐 자료구조 방식
-
넣을 때는 뒤쪽으로, 꺼낼 땐 앞쪽으로 꺼내는 것
따라서 꺼낼 때는 first in first out 방식으로 진행된다
(스택은 last in first out, 나중에 들어간게 먼저) -
파이썬에서는 deque라는 자료구조로 큐를 사용할 수 있다
deque는 앞에서도 넣을 수 있고, 꺼낼 수도 있다
popleft / append
-
deque 사용하는 법
from collection import deque
그리고 k=deque() 이렇게 해주면 k 상대로 popleft(), appendleft(), pop(), append(), popleft() 사용할 수 있다 -
스택에서 list.append와 list.pop()을 이용했던 것처럼 list.append와 list.pop(0)을 이용하면 리스트를 큐처럼 사용할 수 있다. 하지만 pop()의 time complexity는 O(1)인 반면 pop(0)의 time complexity는 O(N)이기 때문에 시간이 오래 걸린다. 따라서 시간 복잡도를 고려해 리스트는 큐로 사용하지 않는다.
