[BOJ]11866번 요세푸스 문제 0 (Python)

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>

해설

원형큐? 순회큐를 이용한 문제라고 하는데, 처음 들어봤다.

나는 파이썬 list로 풀었고 처음에는 list를 재 배열하는 문제로 처음 접근했지만, 재 배열한 리스트를 할당하고 또 그에 따른 처리에 쓸데없는 과정이 들어가서 처음 list를 만들면 k번째 숫자를 print 해주고 리스트에서 제거해주는 방식으로 해결했다.

하면서 이거에 관한 수학적인 방법 혹은 접근이 없을까? 생각을 했지만 내 짧은 수학머리로는 생각이 나지도 않았고 구글링해도 찾지 못하였다.

코드에 대한 구체적인 설명을 해보자면,

n,k = map(int,input().split()) #1
q =[i for i in range(1,n+1)]  #1
print('<',end='')  #2
i = 0   #3
while len(q) > 1: #4
    i = i+k #5
    if i > len(q): #6
        i = i % len(q) #7
        if i == 0 : #8
            i = i+ len(q) #8
    i = i-1 #9
    print(str(q.pop(i)), end=", ") #10
print(str(q.pop())+">") #11

 

변수 초기화

• section 1.

n,k를 입력받고 1부터 n까지의 q라는 리스트를 만든다. 원형 큐 문제라길래 q로 변수명을 사용했다.

• section 2. 

출력 예제를 보면 꺽새('<')부터 시작하기 때문에 print 해준다.

• section 3. 

반복문에서 i라는 변수를 이용해서 내보낼 요소를 가르킬, 일종의 포인터 변수다. 그 변수를 0으로 초기화한다.

 

while문

• section 4. 

len(q) > 0 이 아니라 1인지 의아해 할수도 있는데 마지막에 내보낼 요소는 while문 밖에서 print할 것이기 때문이다.

왜냐하면 숫자마다 사이에 쉼표(,)가 있는데 이것을 반복문으로 내보내는 요소 뒤에 붙여서 프린트할 것이다. 마지막숫자는 뒤에 쉼표가 없기 때문에 while 문 밖에서 print 하도록 한다.

• section 5. 

 i의 k번째를 더해준다. i는 이전에 뺐던 요소의 인덱스를 가르킨 값이다. 첫 루프때는 while 전에 0으로 초기화했기 때문에 0이다. 두번째 루프부터는 이전에 뺀 요소의 인덱스를 가르킬 것이다.

• section 6. 

i가 가르키는 인덱스가 리스트 외부로 벗어났을때, index of range 에러를 처리하기 위해 if문을 걸어준다.

• section 7.

리스트 길이로 나머지 처리를 하면 포인터가 앞으로 돌아와서 그 다음번째 인덱스를 가르킨다.  

• section 8.

만약에 나눴는데 딱 떨어지면 리스트의 길이를 다시 더해서 끝쪽을 가르키게 한다.

• section 9

위에 모든 과정을 거친 i에서 1을 빼주는데, 이유는 0 1 2 3 에서 세번째를 고를때, 2가 나온다 index랑 실제 몇번째인지는 1의 차이가 있기 때문에 빼준다.

• section 10.

그리고 해당 i번째 숫자를 제거하고 그 값에 쉼표를 붙혀서 print해준다. pop은 제거한 요소를 return해주기 때문에 print로 잘 찍힌다.

마지막

• section 11.

리스트의 마지막 하나 남은 요소를 pop하고 꺽새를 닫아준다.