[알고리즘 연습] 요세푸스 문제

• https://www.acmicpc.net/problem/1158

---

풀이

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

num_list = list(range(1,n+1))

idx = k - 1
print("<", end="")
while len(num_list) > 1:
    print(num_list.pop(idx), end=', ')
    idx = (idx+k-1) % len(num_list)
print(f"{num_list.pop(idx)}>")

• 리스트를 활용한 풀이이다.
• k번째 사람은 인덱스 상으로는 k - 1번째 사람이므로 처음 인덱스를 k -1로 부여한다.
• 이 후에도 k - 1씩 더하되, 리스트의 전체 길이보다 커지지 않도록 mod 연산 처리를 해준다.

from collections import deque

n, k = map(int, input().split())
num_list = deque(range(1, n+1))

result_str = ""
while len(num_list) > 0:
    num_list.rotate(-(k-1))
    result_str += f"num_list.popleft(), "

print(f"<{result_str.rstrip(', ')}>")
# rstrip의 명확한 역할파악하기

• deque를 이용한 풀이이다.
• 원리는 동일하다.