https://www.acmicpc.net/problem/11866
11866번: 요세푸스 문제 0
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
www.acmicpc.net
우선 이 문제는 요세푸스 순열을 이해를 해야 풀 수 있는 문제다.
이렇게 사람들이 동그랗게 앉아 있다고 가정해보자.
만약 순서대로 3번째 사람을 제거한다고 문제가 주어지면 제일 먼저 제거되는 사람은 3이다.
그 후, 3이 제거되므로 리스트의 길이도 1 줄어든다.
리스트의 길이를 고려하지 않고 무작정 3번째 인덱스를 pop함수를 이용해 제거한다면 아마 index를 초과했다는 런타임에러 메세지가 나올 것이다.
그러므로 원형큐의 원리를 사용해서 인덱스의 길이로 나눈 나머지를 이용해야 한다.
말로 들으면 잘 이해가 되지 않을 수도 있다. 코드와 함께 설명하겠다.
|
1
2
3
4
5
6
7
8
9
10
11
|
def NoJosep(n,k):
people_list = []
josep_list = []
remove_index = 0
for i in range(1,n+1):
people_list.append(i)
while len(people_list) > 0:
remove_index += k-1
remove_index %= len(people_list)
josep_list.append(str(people_list.pop(remove_index)))
return josep_list
|
cs |
우선 사람들의 번호를 순서대로 넣는 people_list, 함수의 반환값인 요세푸스 순열 값이 담긴 josep_list, 삭제할 인덱스 정보가 있는 remove_index를 만든다.
그 후, poeple_list에 for 반복문을 사용해서 사람들을 순서대로 넣는다.
while(len(people_list) > 0 반복문은 people_list에 값이 없어질 때까지 무한반복 한다는 소리다. pop(1)을 하면 인덱스 기준 첫 번째 사람이 없어진다. 즉 2가 없어진다는 소리다. 그러므로 우리는 k(번째)-1을 함으로써 k번째 사람을 제거한다. remove_index %= len(people_list)는 우리가 pop을 계속해서 하다 보면 K보다 people_list의 길이가 더 작아질 때가 있다. 그럴 때를 위해 remove_index를 people_list의 길이로 나눈 다음 나머지 값으로 pop을 한다.
정답 코드:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
N,K = map(int,input().split())
def NoJosep(n,k):
people_list = []
josep_list = []
remove_index = 0
for i in range(1,n+1):
people_list.append(i)
while len(people_list) > 0:
remove_index += k-1
remove_index %= len(people_list)
josep_list.append(str(people_list.pop(remove_index)))
return josep_list
josep_list = NoJosep(N,K)
print("<%s>" %(", ".join(map(str,josep_list))))
|
cs |
