[Python Algorithm] 자료구조(큐) - 공주 구하기

> 자료구조 활용 - 스택, 큐, 해쉬, 힙 (큐 편)
: 큐는 FIFO, 파이썬에서 큐를 자료구조를 제공하는 것은 deque
- deque -
앞에서 넣으면 (appendleft)  <-- ------------- <-- 뒤에서 넣으면 (append)
앞에서 꺼내면 (popleft)         --> ------------- --> 뒤에서 빼면 (pop)

 

📖 문제  :  공주 구하기

정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔습니다.

정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 합니다. 정보왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했습니다.

왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매긴다. 그리고 1번 왕자부터 N 번 왕자까지 순서대로 시계 방향으로 돌아가며 동그랗게 앉게 한다. 그리고 1번 왕자부터 시 계방향으로 돌아가며 1부터 시작하여 번호를 외치게 한다. 한 왕자가 K(특정숫자)를 외치면 그 왕자는 공주를 구하러 가는데서 제외되고 원 밖으로 나오게 된다. 그리고 다음 왕자부터 다시 1부터 시작하여 번호를 외친다.
이렇게 해서 마지막까지 남은 왕자가 공주를 구하러 갈 수 있다.

예를 들어 총 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

 

출력예제 1
7

 

import sys
from collections import deque

n, k = map(int, input().split())
queue = list(range(1, n+1))
queue = deque(queue)		#	리스트인것을 deque로 !

while queue:
    for _ in range(k-1):		#	2명을 뒤로 다시 넣는다. 
    	temp = queue.popleft()
        queue.append(temp)
    queue.popleft()		#	3번째 된 왕자 제거 !
    if len(queue)==1:
    	print(queue[0])
        break

 

⭐️ Point ! ⭐️

• list1 = deque(list1)
  리스트인 것을 deque로 만들기
  
  
• deque의 앞의 것을 제거하기 위한 함수 popleft()

 

 

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이