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

 

문제 분석

• 1부터 N번까지 N명의 사람이 원을 이루며 앉아있고
• 양의 정수 k가 주어짐
• 순서대로 k번째 사람 제거
• 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속 함
• N명의 사람이 모두 제거될 때 까지 계속

 

코드 설계

• 제거된 수에 대해 +3 위치의 숫자 제거
• 앞의 2개 빼서 뒤로 보내고 마지막 3번째 pop해서 출력하기에는.. 너무 복잡하지 않나..

 

정답 코드

import sys
input = sys.stdin.readline

from collections import deque

n, k = map(int, input().split())
d = deque([i for i in range(1, n+1)])
ans = []

while len(d) > 0 :
    for _ in range(k-1) :
        tmp = d.popleft()
        d.append(tmp)
    ans.append(d.popleft())

print('<', end='')
for i in range(len(ans)) :
    print(ans[i], end='')
    if i < len(ans)-1 :
        print(', ', end='')
print('>')

 

다른 사람 코드 1

import sys
from collections import deque

# 입력 받기
n, k = map(int, input().split())

# 양방향 연결 리스트(deque) 생성
deq = deque([i for i in range(1, n+1)])

# 요세푸스 순열 생성
res = []
while len(deq) != 0:
    for _ in range(k-1):
        # k-1번째 노드까지 deq 맨 뒤로 이동
        deq.append(deq.popleft())
    # k번째 노드 삭제 후 결과 배열에 추가
    res.append(str(deq.popleft()))

# 결과 출력
print('<'+', '.join(res)+'>')