[python] 백준 1158번 요세푸스 문제

문제 요약 및 풀이

입력이 7 3일 때 (1 2 3 4 5 6 7) 번까지 총 7명의 사람이 원을 이루고 있게 되고 3번째 사람을 제거하게 되는데 표로 보여주겠다. 

 

리스트를 이용해서 풀면 되겠다 싶었다. 배열의 index값은 0번째부터 시작이니 k=3이라면 list[2]라고 생각하면 된다.

K번째 사람이 제거 될때마다 리스트의 사이즈가 하나씩 줄어드는 걸 볼 수 있다.

1	2	3	4	5	6	7
[0]	[1]	[2]	[3]	[4]	[5]	[6]

3

1	2	4	5	6	7
[0]	[1]	[2]	[3]	[4]	[5]

6

1	2	4	5	7
[0]	[1]	[2]	[3]	[4]

2

1	4	5	7
[0]	[1]	[2]	[3]

7

1	4	5
[0]	[1]	[2]

5

1	4
[0]	[1]

1

4

[0]

4

 

빨간색만을 보면 규칙이 있다. n번까지 원형으로 앉아있기 때문에 순환이 된다.

그래서 생각해본 식이 i = (i + (k-1)) % len(queue) 이다.

 

당연히 위와 같은 식을 만들어내기 위해서 시간과 노가다를 해야 하는 점이 있었다...

전공 수업시간에 자료구조 좀 잘해놓을걸... ㅠㅠ

 

우여곡절 끝에 완성된 코드!! 😊👍

N, K = map(int, input().split())

queue = []
result = []
for i in range(1, N + 1):
    queue.append(i)

i = 0
while queue:
    i = (i + (K - 1)) % len(queue)
    result.append(queue.pop(i))

print("<" + ", ".join(map(str, result)) + ">")