문제
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
링크 참조
풀이 설명
원으로 가정하고 K번째 만큼 index을 구했을 때 나오는 순서대로 출력하면 된다.
구한 index은 없어지고 그 이후 K번째를 구하는 것으로 지워지는 것을 잘 감안해야 하는 문제이다.
코드
N, K = map(int,input().split())
people = []
answer = []
for i in range(1,N+1):
people.append(i)
index = K - 1
key = 0
while people:
key = (key+index) % len(people)
answer.append(people.pop(key))
print('<'+', '.join(map(str,answer))+'>')index은 K번째보다 1을 빼준 값이어야 한다. (배열 특성)
people에 1부터 N번째까지를 담았다. 따라서, people이 아무것도 없을 때까지 반복한다.
key로 해당되는 index 값을 꺼낼 것이다.
- pop() 이용 한다.
ex) A.pop(index) 을 하면 A 배열의 index에 해당되는 값이 꺼내지게 된다.
아예 꺼내지고 지워짐!
꺼낸 값을 answer이라는 배열에 다시 넣어놓는다.
이 문제는 index를 더해짐에 따라 달라지는 길이만큼 나누게 되면 새로운 key가 되는 것을
알아내는 것이 가장 중요했다.
💌
후기
규칙을 찾는 것이 쉽지는 않았다.
다시 한번 보면 좋을 것 같은 문제 !
beginner :>