Python / 11866 요세푸스문제

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

11866번: 요세푸스 문제 0

 

백준의 알고리즘 문제 중 요세푸스 문제이다 

 

문제는 1번부터 N번까지의 N명의 사람이 원을 이루고 있다고 가정하고 K의 양의정수가 주어진다 

그다음 순서대로 K번째사람을 제거한다 이 과정을 N명의 사람이 모두 제거될때까지 반복하는것이다

 

처음 작성한 코드이다

 

3 6 2 까지는 잘 됐지만 그다음부터 문제가됐다 

q가 len(puss)보다 커지면 나머지로 바꿔주는 부분이 잘못됐던것 같다

 

이후에 계속 고민을 하다 결국 검색을해서 답을 봤다

from sys import stdin

n, k = map(int, stdin.readline().split())
puss = list(i for i in range(1, n+1))
answer = list()
k -= 1

for i in range(1, n+1):
  q = k*i
  if q > len(puss):
    q = q % len(puss)
  answer.append(puss.pop(q))
for i in answer:
  print(i, end=' ')

 

검색을 해서 구현한 문제

from collections import deque
from sys import stdin

n, k = map(int, stdin.readline().split())
puss = deque(i for i in range(1, n+1))

print('<', end='')
while puss:
    for i in range(k-1):
        puss.append(puss.popleft())

    print(puss.popleft(), end='')
    if puss:
        print(',', end=' ')

print('>')

덱을 이용해서 풀이를 했다 맨 위에 import를 해주고 

n, k를 입력받는다

그다음 puss라는 이름의 덱을 선언해주고 그 안을 n만큼 채워준다

 

그다음 k번째 순서대로 출력해줘야 하는데 while문으로 puss안의 원소가 모두 제거될때 까지 반복해준 뒤

for문으로 k - 1 만큼 뒤로 넘겨준다 그 후 print문으로 k번째 사람을 출력해주고 제거해준다

이걸 반복한다

 

 

 

첫번째 코드에는 나름 공식을 만들어본다고 생각해본것인데 덱을 사용해서 푸는건 생각하지못했다 여러방향으로 생각해보아야 겠다.