문제
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 77745 | 44033 | 36893 | 56.428% |
문제 설명
요세푸스 문제는 다음과 같다.
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.
N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)
출력
예제와 같이 요세푸스 순열을 출력한다.
예제 입력 1
7 3예제 출력 1
<3, 6, 2, 7, 5, 1, 4>내 풀이
문제의 이해
우선 문제 자체를 이해했는지를 물어보는 게 먼저다..
문제의 예제 출력 자체를 이해하지 못했다^^(걍빡대갈)
그래서 구글에 "요세푸스 문제"라고 치니 상세하고 친절하게 설명해주신 블로거분들이 많았다. 그들의 게시물을 참고했는데도 이해하지 못한 나 ..
결국 한 움짤을 보고 이해에 성공했다 ^_^
이런식의 원으로 배치된 사람들이 k번째 인간을 죽이며 마지막 사람이 남을때까지 계속하는 게임이었던 것..!
위의 문제에서 나온 예제를 바탕으로 원을 그려 이해해보기도 했다.
순서대로 문제를 진행하면 3 -> 6 -> 2 -> 7 -> 5 -> 1 -> 4 순으로 죽게된다.
문제 풀이 아이디어
그렇다면 이 문제는 과연 어떻게 푸는 것인가
스택 LIFO 방식의 스택 구조가 아닌, FIFO 방식의 큐 구조로 문제를 풀면 시간초과 없이 문제를 해결할 수 있다.
첫번째 사람을 죽일때, 이미 지나간 1과 2의 사람은 우선순위에서 밀리게 된다. 이를 queue의 popleft와 append를 이용해 구현한다. ->
그럼 [1,2,3,4,5,6,7] -> 3은 죽고 [4,5,6,7,1,2] 의 우선순위
같은 방식으로 두번째 사람이 죽고 나서는 [7,1,2,4,5] 의 우선순위를 갖게 될 것이다.
코드
위 아이디어를 바탕으로 코드를 구현해보았다.
# 11866번 실버5
# 요세푸스 문제0
from collections import deque
n, k = map(int, input().split())
people = [i+1 for i in range(n)]
people = deque(people)
result = []
while people: # 리스트안에 데이터가 존재할때까지
for _ in range(k-1): # 0부터 k-1까지
people.append(people.popleft()) # 맨 앞의 값을 맨 뒤로
result.append(str(people.popleft())) # k번째 값을 result 리스트로
print("<"+", ".join(result)+">") # 위의 코드에서 str을 추가하지 않으면 출력이 제대로 되지 않는다.
파이썬에서는 collections 라이브러리의 deque 모듈을 사용해 queue를 구현할 수 있다.
deque는 append, appendleft, pop, popleft 모두 시간복잡도가 O(1)인 사기적인 자료구조이다.
초기 입력값을 담는 people과 결과 값인 요세푸스 순열을 담을 result를 생성해주었다.
여기서 주의해야할 점은, result에 append 해줄때 people 원소의 값이 int형이므로, 타입을 str형으로 바꿔서 append 해줘야 마지막 print문에서 오류가 발생하지 않는다.
