Algorithm - 공주 구하기(큐)

 

알고리즘 입문 수업을 듣고 중요한 내용을 정리했습니다.
개인 공부 후 자료를 남기기 위한 목적이므로 내용 상에 오류가 있을 수 있습니다.

 

문제

[공주 구하기(큐)]

 

정보 왕국의 이웃 나라 외동딸 공주가 숲속의 괴물에게 잡혀갔다. 정보 왕국에는 왕자가 N명이 있는데 서로 공주를 구하러 가겠다고 하는 상황이다. 정보 왕국의 왕은 다음과 같은 방법으로 공주를 구하러 갈 왕자를 결정하기로 했다.

 

왕은 왕자들을 나이 순으로 1번부터 N번까지 차례로 번호를 매겨, 1번 왕자부터 N번 왕자까지 시계 방향의 순서대로 동그랗게 앉게 했다. 그리고 1번 왕자부터 시계 방향으로 돌아가며 1부터 번호를 외치게 한다. 이 때, 어떤 왕자가 K(특정순서)번을 외치면 그 왕자는 공주를 구하러 가는 일에서 제외된다. 이러한 과정을 반복하여 마지막까지 남은 왕자가 공주를 구하러 가는 것이다.

 

예를 들어 총 8명의 왕자가 있고, 3을 외친 왕자가 제외된다고 하자.

처음에는 3번 왕자가 3을 외쳐 제외된다. 이어 6번 왕자, 1번 왕자 순으로 왕자들이 차례대로 제외되어 결국 마지막에 남는 7번 왕자가 공주를 구하러 가게된다. N과 K가 주어질 때, 공주를 구하러 갈 왕자의 번호를 출력하는 프로그램을 작성하시오.

 

 

*입력 설명

첫 번째 줄에는 자연수 N(5 ≤ N ≤ 1,000)과 K(2 ≤ K ≤ 9)가 주어진다.

 

*출력 설명

첫 번째 줄에 마지막 남은 왕자의 번호를 출력한다.

 

 

---

 

 

풀이(Python)

답안

import sys
from collections import deque 
sys.stdin = open('AA/input_36.txt', 'rt')

n, k = map(int, input().split())
dq = list(range(1, n+1))
dq = deque(dq)

while dq:
    for _ in range(k-1):
        cur = dq.popleft()
        dq.append(cur)
    dq.popleft()
    if len(dq) == 1:
        print(dq[0])
        dq.popleft()
        
# 출력 : 7

 

input_36.txt(입력)

8 3

 

 

중요내용

1. 큐 자료구조는 First in, First out 구조이다.
2. 즉, 먼저 들어간 데이터가 먼저 추출되는 방식이다. (스택 자료구조와 상반된 개념)
3. 파이썬은 collections 라이브러리를 통해 deque라는 자료형을 제공하며 이를 통해 큐 자료구조의 매커니즘을 구현할 수 있다.
4. 파이썬의 append() 함수와 popleft() 함수를 사용하여, 큐 자료형의 데이터를 조작할 수 있다.
5. 참고로, 위의 문제를 해결하는 방법 중 하나는 원형의 데이터를 일자 형태의 정렬된 데이터로 간주하는 것이다.
6. deque 자료형의 첫 번째 데이터부터 K-1번째 데이터 까지 모두 popleft() 함수로 추출하여, 순서를 유지한채 append() 함수로 deque 자료형의 마지막 부분에 그대로 넣어준 후, popleft() 함수를 한 번더 사용하여 K번째의 데이터를 추출하고 제거한다.
7. 이러한 방식을 반복 실행하여 결국 deque 자료형의 데이터를 1개만 남긴다. (이렇게 남은 데이터가 정답임)
8. 위의 답안에서 마지막의 dq.popleft()는 while문의 break 역할을 하는 코드이다. (break문을 써도 무방함)