백준 1158 문제 링크: https://www.acmicpc.net/problem/1158
📑 문제 설명
요세푸스 순열을 프로그래밍 하는 문제이다.
예를 들어, 7명의 사람이 있고 3번째 사람을 계속 제거한다면
1, 2, [3], 4, 5, 6, 7 --> 3 제거
1, 2, [3], 4, 5, [6], 7 --> 6 제거(6이 제거된 다음 7이 첫번째가 됨)
1, [2], [3], 4, 5, [6], 7 --> 2 제거
1, [2], [3], 4, 5, [6], [7] --> 7 제거
1, [2], [3], 4, [5], [6], [7] --> 5 제거
[1], [2], [3], 4, [5], [6], [7] --> 1 제거
[1], [2], [3], [4], [5], [6], [7] --> 4 제거
<3, 6, 2, 7, 5, 1, 4> 순열이 요세푸스 순열을 의미한다.
입력: 사람 수와 제거할 순번을 입력
출력: 입력에 따른 요세푸스 순열 출력
💡 문제 해결 방법
원형으로 이루어진 큐를 사용하여 문제를 푸는 것이 이해가 가장 잘 됐다.
예를 들어 입력이 7 3 이라면,
초기 사람 리스트: 1, 2, 3, 4, 5, 6, 7 로 구성된다. 그럼 차례대로
1 2 3 4 5 6 7 --> 첫번째 사람이므로 queue에 push
2 3 4 5 6 7 1 --> 두번째 사람이므로 queue에 push
3 4 5 6 7 1 2 --> 세번째 사람이 나왔으니 3번째는 pop --> 3
4 5 6 7 1 2 --> 첫번째 사람이므로 queue에 push
5 6 7 1 2 4 --> 두번째 사람이므로 queue에 push
6 7 1 2 4 5 --> 세번째 사람이 나왔으니 3번째는 pop --> 6
7 1 2 4 5 --> 첫번째 사람이므로 queue에 push
1 2 4 5 7 --> 두번째 사람이므로 queue에 push
2 4 5 7 1 --> 세번째 사람이 나왔으니 3번째는 pop --> 2
.
.
.
queue에 더이상 사람이 없을 때까지 반복하여 요세푸스 순열을 얻을 수 있다.
나는 계속 틀려서 정답과 내 답을 비교한 결과, 나머지 연산을 사용하여 인덱스를 설정함을 확인했다.
1 2 3 4 5 6 7 --> 3, 6 제거(index 2, 4(3을 pop 하면 index가 줄어듦))
1 2 4 5 7--> 2, 7 제거 (index 1, 3)
1 4 5--> 5 제거 (index 2)
1 4 --> 1 제거 (index 0)
4 --> 4 제거 (index 0)
한 행마다 제거되는 index는 index, index + 2, index + 2 + 2 ... 순서임을 알 수 있으며,
index가 queue.size 보다 클 경우에는 나머지 연산을 취하여 index를 초기화한다.(두번째 행 경우, 6 % 5 = 1)
이 과정을 반복하여 queue에 남은 원소가 없을 때까지 반복한다.
위에 예시로 든 행 마다 index를 초기화해준다는 사실을 이해하고 정답코드를 보면 이해에 도움이 될 것이다.
💻 코드
꾸망쓰 코드
import sys
def Josephus(queue, K):
result = list()
for i in range(len(queue)):
if (len(queue)>K):
for i in range(K - 1):
queue.append(queue.pop(0))
result.append(queue.pop(0))
elif (len(queue) <= K):
result.append(queue.pop(K%len(queue) - 1))
return result
if __name__ == '__main__':
N, K = map(int, sys.stdin.readline().split())
queue = list()
for i in range(1, N + 1):
queue.append(i)
result = Josephus(queue, K)
print('<', end='')
for i in range(N):
if (i != N -1):
print(f'{result[i]}, ', end="")
else:
print(f'{result[i]}', end="")
print('>', end="")
정답 코드
import sys
def Josephus(queue, K):
result = list()
num = K - 1
for i in range(len(queue)):
if (len(queue)>num):
result.append(queue.pop(num))
num += K - 1
elif (len(queue) <= num):
num = num%len(queue)
result.append(queue.pop(num%len(queue)))
num += K - 1
return result
if __name__ == '__main__':
N, K = map(int, sys.stdin.readline().split())
queue = list()
for i in range(1, N + 1):
queue.append(i)
result = Josephus(queue, K)
print('<', end='')
for i in range(N):
if (i != N -1):
print(f'{result[i]}, ', end="")
else:
print(f'{result[i]}', end="")
print('>', end="")
💟 추가적으로 알게 된 점
- 왜 내 코드는 안될가요?
