[Python] 백준 11866 : 요세푸스 문제 0

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

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

---

📌 문제 탐색하기

어떻게 접근하면 좋을지 고민하던 과정에서 큐(queue)라는 개념을 활용하면 좋을거 같았다.

이것도 자료구조 시간 때 분명 배웠었는데 기억이 정확히는 안 나는 관계로 조금 더 알아보았다.

 

큐(Queue)란?

큐는 양쪽이 뚫여있는 긴 통에서 한 쪽은 데이터를 삽입하고, 다른 한 쪽은 데이터를 삭제하는 구조이다.

큐는 먼저 들어간 데이터가 먼저 나오는 '선입선출(FIFO-First In, First Out)' 구조이다.

cf) 스택은 후입선출(LIFO-Last in, First Out)

 

 파이썬에서 제공하는 Queue 모듈을 활용하면 조금 더 쉽게 구현할 수 있다.

//큐 모듈 임포트
import queue 

//큐 객체 생성(Maxsize는 큐의 최대 사이즈)
q = queue.Queue(Maxsize)

//큐 요소 삽입 함수
q.put(item)

//큐 요소 꺼내는 함수
q.get()

//큐가 비어있는지 확인하는 함수
q.empty()

//큐가 가득찼는지 확인하는 함수
q.full()

 

아...근데...큐를 공부하면서 한가지 문제를 깨달았다...

이 문제에서는 첫 번째 인덱스를 출력하는게 아니라 원하는 임의의 인덱스 값을 구할 수 있어야 했다.

그래서 그 대안으로 알게 된게 데크(Deque)였다.

 

데크(Deque)

데큐는 'double-ended que'의 약자로 스택과 큐를 일반화 한 것이다.

그렇기 때문에 양방향에서 데이터를 추가 및 제거할 수 있는 자료구조이다.

//임포트
from collections import deque

//데크 객체 생성
dq = collections.deque()

//오른쪽으로 삽입
dq.append(i)

//왼쪽으로 삽입
dq.appendleft(i)

//왼쪽 요소 삭제
dq.popleft()

//오른쪽 요소 삭제
dq.pop()

//오른쪽으로 n만큼 요소 회전
dq.rotate(n)

//왼쪽으로 n만큼 요소 회전
dq.rorate(-n)

 

=> 그래서 결론은! queue가 아닌 deque를 활용하여 문제를 풀면 된다는 것이다!!!

     (무엇보다 deque는 스택과 큐를 모두 포함하니까 앞으로 이런 문제 있으면 고민 없이 그냥 deque 사용하면 될거 같다!)

---

📌 코드 설계하기

1. 입력값 가져오기

-> N, K

 

2. deq 리스트 값 할당

-> 1부터 N+1까지의 값

 

3. k번째 값 출력

-> for문으로 N번 반복

-> 왼쪽으로 k번 이동하여 [0]번째 값 popleft()

 

4.  출력

-> <3,6,1,>과 같은 형식에 맞춰 값을 출력해야 한다.

-> 현재 deq 배열 형태는 [1,2,3,]과 같은 숫자 배열이다.

-> 이를 형식에 맞도록 바꾸기 위해서는 우선 문자열(str)로 바꾼 다음, join()을 활용하여 배열로 출력해야 한다.

-> 출력할 때 콤마(,)를 기준으로 해야하므로 ", ".join(map(str,deq))

---

📌 정답 코드

import sys
from collections import deque

input=sys.stdin.readline
N,K=map(int,input().split())
result=[]

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

for _ in range(N):
    deq.rotate(-(K-1))
    result.append(deq.popleft())

print("<"+", ".join(map(str,result))+">")

 

해설 : https://whydevsaysno.notion.site/0-e2cae66133c44e3aaadefc374ad3f3b7