백준 파이썬 11866번 요세푸스 문제 0 (Today I Learn 2023.11.05)

11/ 05 파이썬 공부
1. 백준 11866번 요세푸스 문제 0

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

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

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

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

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

>>>코드1: 리스트만 이용하기

n, k = map(int, input().split()) # n, k 입력받기
l = list(i for i in range(1, n+1)) # 1~n 까지의 숫자로 이루어진 리스트 생성
result = [] # 최종 순서를 기록할 리스트
while l:
    for i in range(k-1):
        l.append(l[0]) # k만큼 앞의 숫자를 뒤에 저장
        del l[0] # 맨 앞 숫자 삭제
    result.append(l[0]) # 결과 저장
    del l[0] # 맨 앞 숫자 삭제
print('<', end = '') # 출력 기준에 맞게 출력
for i in range(len(result)-1):
    print(result[i], end = ', ')
print(result[-1], end = '')
print('>')

n, k 를 입력받아 리스트를 만들고, 

맨 앞의 요소를 뒤로 보내면서 해당 순서의 숫자를 새 리스트에 저장했으나 조금 복잡해 보였다.

그래서 찾아보니 전에 배운 덱을 파이썬에서 사용할수 있는 모듈이 있었다.

>>>코드 2: from collections import deque 이용하기

from collections import deque
n, k = map(int, input().split()) # n, k 입력받기
d = deque([i for i in range(1, n+1)]) # 1~n 까지의 숫자로 이루어진 덱 생성
result = [] # 최종 순서를 기록할 리스트
while d:
    for i in range(k-1):
        d.append(d.popleft()) # k만큼 앞의 숫자를 뒤에 저장 및 맨 앞 숫자 삭제
    result.append(d.popleft()) # 결과 저장 및 맨 앞 숫자 삭제
print('<', end = '') # 출력 기준에 맞게 출력
for i in range(len(result)-1):
    print(result[i], end = ', ')
print(result[-1], end = '')
print('>')

큰 틀은 비슷한데 속도는 빨라진 모습을 확인할 수 있다.

>>> 코드 설명: from collections import deque
덱을 파이썬에서 사용할 수 있는 모듈이다.

1) 덱 만들기
d = deque(덱에 들어갈 요소)

2) 스택 구현
- d.append(): 마지막(오른쪽 끝)에 요소 저장
- d.pop(): 마지막 요소 삭제

3) 큐 구현
- d.appendleft(): 처음(왼쪽 끝)에 요소 저장
- d.popleft(): 처음 요소 삭제

4) 덱 확장
- d.extend(): 오른쪽으로 덱 확장, 마지막에 요소들 추가
- d.extendleft(): 왼쪽으로 덱 확장, 처음에 요소들 추가

5) 리스트 처럼 사용
- d.remove(): 특정 요소 삭제 (중복시 인덱스가 가장 작은 것 하나만 삭제)
- d.insert(인덱스, 요소): 입력한 인덱스에 요소 추가

6) 덱 반전
- d.reverse(): 순서 반대로 만들기

-문제 링크
https://www.acmicpc.net/problem/11866