[백준/파이썬] 1168번 요세푸스 문제 2 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1168번 요세푸스 문제 2
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

요세푸스 순열을 출력하는 문제로, N명이 원형으로 있고 K번째 사람을 반복 제거합니다.

코드

class Node:
    def __init__(self,value, nxt=None):
        self.value = value
        self.nxt = nxt
n, k = map(int, input().split())
start = node = Node(0)
for i  in range(1, n+1):
    tmp = Node(i)
    node.nxt = node = tmp
node.nxt, node = start.nxt, start

result = []
for _ in range(n):
    t = k % (n - len(result)) - 1
    for __ in range(t):
        tmp, node = node, node.nxt
    result.append(node.value)
    tmp.nxt = node.nxt
print("<"+", ".join(map(str, result))+">")

설명

원형 연결리스트를 구성하고 남은 인원 수에 대해 k % 남은인원만큼 이동해 제거할 노드를 찾습니다.

매 단계마다 제거된 값을 저장하고, 마지막에 요구 포맷으로 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---