S4 1158. 요세푸스 문제

문제 보기 :  1158번: 요세푸스 문제

---

문제

• 정답률 : 49%

---

작성 코드

# 입력: 총 인원 수와 제거 주기
a, b = map(int, input().split())

from collections import deque

# 1부터 a까지의 번호를 deque에 저장
lst = deque(range(1, a + 1))
answer = []  # 제거된 순서를 저장할 리스트

# 순차적으로 사람을 제거
for i in range(1, 5000 * 5000):  # 충분히 큰 반복 횟수 설정
    if len(answer) == a:  # 모든 사람이 제거되면 종료
        break
    if i % b == 0:  # 제거 주기에 도달한 경우
        answer.append(str(lst.popleft()))  # 제거된 사람을 결과 리스트에 추가
    else:  # 제거 주기가 아닌 경우
        lst.append(lst.popleft())  # 맨 앞 사람을 맨 뒤로 이동

# 출력 형식 맞추기
print('<', end='')
print(", ".join(list(answer)), end='')
print('>', end='')

---

풀이

1부터 a까지의 사람들을 원형으로 배열한 후, b번째 사람을 순서대로 제거하면서 제거된 순서를 출력한다.

deque를 사용해 순서를 관리하는데 b의 배수일 때는 현재 사람(맨 앞 값)을 제거해 정답 리스트에 추가하고, 그렇지 않으면 맨 앞의 사람을 맨 뒤로 이동시킨다.

모든 사람이 제거되면 결과 리스트를 <숫자1, 숫자2, ..., 숫자n> 형식으로 출력한다.