[python/파이썬] 백준 11866 요세푸스 문제 0

[문제 출처]

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

11866번: 요세푸스 문제 0

 

[문제 풀이]

n과 k가 주어졌을 때, 1번부터 n이 원형으로 배치되어 있고, k번째 숫자를 제거해야 한다.

 

만일 n=7, k=3이라고 한다면,

 

1 2 3 4 5 6 7

4 5 6 7 1 2

7 1 2 4 5

4 5 7 1

1 4 5

1 4 (1 4 1)

4

 

위와 같은 순서대로 제거된다. k번째 숫자를 제거하고 그다음부터 다시 k번째에 위치한 숫자를 제거하게 된다.

 

큐를 이용해 계속해서 첫번째 원소를 제거해서 다시 해당 큐에 저장해주는 방식으로 원형을 구현하였고,

k번째일 때는 제거 후 결과 리스트에 저장한다.

결과를 출력할 때 join함수를 사용할 것이므로 문자 형태로 저장해준다.

#11866

from collections import deque

queue = deque()
result = []

n, k = map(int, input().split())

for i in range(1,n+1):
  queue.append(i)

while 1:
  for i in range(k-1):
    tmp = queue.popleft()
    queue.append(tmp)
  result.append(str(queue.popleft()))

  if len(queue)==0:
    break

print('<'+ ", ".join(result)+'>')