요세푸스 순열을 구현하는 문제이다.
이 문제의 관건은 K번째의 사람을 제거하고 제거한 사람으로 부터 K번째를 다시 세서 제거해야 한다는 점이다.
초기 코드
N, K = map(int, input().split())
arr = list(range(1,N+1))
result = []
T = K
for i in range(N):
if len(arr) < T:
T = T % (len(arr))
if (T-1) < 0:
T = K
elif len(arr) == 1 and T == 0:
T = 1
print(arr, T-1, result)
result.append(arr.pop(abs(T-1)))
T += (K-1)
맨 처음에 짠 코드는 아래와 같다. N명의 사람을 제거해야 하므로 for문은 for i in ragne(N)과 같이 돌렸으며 K번째 사람을 제거해야 하므로 T라고 하는 변수를 저장해 K번째 사람을 계속 해서 제거할 수 있도록 코드를 구성하였다.
하지만 위 코드는 남은 인원이 K보다 같거나 작아질 때 충돌이 일어나 제대로 활용할 수 없었다.
두 번째 코드
N, K = map(int, input().split())
arr = list(range(1,N+1))
result = []
for i in range(N):
arr = arr[K:] + arr[:K]
result.append(arr.pop())
print(result)그렇게 수정한 두 번째 코드는 다음과 같다.
힌트에 '큐'가 있었던 점을 활용하여 배열을 매번 K번째 값이 맨 끝으로 가게 변경한 후 pop()하여 저장하는 형태로 변경한 것이다. 하지만 이 코드도 마찬가지로 arr 배열의 길이가 K보다 작아질 때 제대로 카운트 하지 못 해 충돌이 일어나는 문제가 발생하였다.
최종 코드
# 초기화된 리스트 생성
arr = list(range(1, N + 1))
result = []
# 시작 인덱스 설정
idx = 0
# 리스트의 길이가 0이 될 때까지 반복
while arr:
# 다음으로 제거될 요소의 인덱스 계산
idx = (idx + K - 1) % len(arr)
# 결과에 해당 요소 추가
result.append(arr.pop(idx))
# 결과 출력
print("<" + ", ".join(map(str, result)) + ">")
#인덱스 계산을 해주는 방식으로 변경최종적으로 수정한 코드는 위와 같다. 첫 번째 코드에서는 len(arr) < K일 때만 인덱스 값인 T를 arr 길이로 나누어주었는데 매번 해당 길이로 나누어줘 문제를 해결하였다.
