[파이썬] 11866번 : 요세푸스 문제 0

https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

문제

요세푸스 문제는 다음과 같다.

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>

 

생각

'''                       인덱스 번호
1 2 3 4 5 6 7              2
3 
1 2 4 5 6 7                4        
6 
1 2 4 5 7                  1
2
1 4 5 7                    3
7
1 4 5                      2
5
1 4                        
1
4 
'''

리스트로 구현해 pop을 해내는 형식으로 해보자라고 접근

k로 주어진 것을 인덱스로 나타낸다면 -1한거로 해야한다.

그리고 한가지의 규칙이 발생했다 k가 홀수 이면 리스트가 2개가 남았을때 인덱스 0 다음 인덱스 1이 호출되고 k가 짝수면 인덱스 1 다음 인덱스 0이 호출된다.

이런 방식으로 코드를 작성해봤다.

import sys
n ,k = map(int,sys.stdin.readline().split())
person_list=[i for i in range(1,n+1)]

count=0
print("<",end='')
for _ in range(n):
    if len(person_list) == 2:
        if k%2==1:
            print(person_list[0],person_list[1], sep=', ',end='')
        else:
            print(person_list[1], person_list[0], sep=', ',end='')
        break
    elif len(person_list) == 1:
        print(person_list[0], end='')
        break
    count+=k-1
    if count>=len(person_list):
        count-=len(person_list)
    print(person_list[count], end=', ')
    del person_list[count]
print(">")

 

제출했더니 IndexError가 났다.

실제로 1000에 해당하는 것과 500을 넣어서 테스트를 해봤더니 오류가 났다. 내 로직에 오류가 있다는 것이었다. 

count-=len(person_list)

의 결과가 index범위가 넘어가는 경우가 생기는 것을 발견했다.

 

다른 접근 법을 이용해야겠다라고 생각을 하게 되는 계기였다.

 

 

다른풀이를 찾아보았다.

덱을 이용해서 했다. 덱을 이용하면 k-1번째까지는 그냥 pop을 하고 다시 뒤에다 넣어주고 k번째가는 출력을 하도록 하는 것을 이용했다.

from collections import deque
 
n,k = map(int,input().split())
q = deque()
 
for i in range(1,n+1):
    q.append(i)

print("<",end='')
while q:
    for _ in range(k-1):
        q.append(q.popleft())
    print(q.popleft(),end="")    
    if q:
        print(", ",end="")
 
    
print(">")

덱에 있는 것이 없을 때까지 while문을 돌고 덱에 아직 원소가 남아있다면 , 를 호출하는 형식으로 했다.