[백준 11866번-요세푸스 문제 0]-파이썬

solved.ac 난이도 :  silver4

백준    11866 번- 파이썬 풀이

 

<문제>

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

11866번: 요세푸스 문제 0

<풀이>-시뮬레이션

keypoint : K번째 수를 구하기 위해선 배열에서 인덱스를 K로 나눴을때의 나머지가 K-1인 인덱스를 구하면 된다.

 

배열과 배열의 인덱스를 을 큐에 넣은 다음 하나씩 큐에서 꺼낸다.

 

큐에서 추출한 원소의 인덱스가 위 keypoint를 만족한다면 result 배열에 삽입한다.

 

큐에서 추출한 원소의 인덱스가 위 keypoint를 만족하지 않는다면 추출된 인덱스에 큐의 길이를 더해서 큐의 맨 마지막부분에 삽입한다.

 

위 과정을 큐가 빌때까지 반복한다.

 

위 과정을 살펴보면 다음과 같다. 예시는 문제에 나온 7,3으로 하자.

 

원소	1	2	3	4	5	6	7
인덱스	0	1	2	3	4	5	6

(1,0),(2,1)추출->0,1 : 위 keypoint를 만족하지 않는다. 이때 큐의 길이는 7이므로 (1,7),(2,8)을 큐에 삽입한다.

 

(3,2)추출 ->2 : 위 keypoint를 만족한다. 따라서 result배열에 3을 삽입한다. 이때 큐의 길이는 6이 된다.

원소	4	5	6	7	1	2
인덱스	3	4	5	6	7	8

최종적으로 result배열이 완성되고 나면 join함수를 통해 문제에서 요구하는 출력형식을 맞추어서 출력한다.

728x90

<코드>-파이썬

#k번째  = K로 나눴을때 인덱스가 K-1에 해당하는 숫자
n,k = map(int,input().split())
from collections import deque
circle = []
for i in range(n):
    circle.append((i+1,i))
queue = deque(circle)
result = []
answer = "<"
while queue:
    length = len(queue)
    a,b  = queue.popleft()
    if b%k == k-1:
        result.append(a)
    else:
        queue.append((a,b+length))
    
a = ", ".join(str(i) for i in result)
answer = answer+a+">"
print(answer)

-마치며-

k번째 수를 찾아내는 아이디어는 생각보다 어렵진 않았다.

다만 어느 구현문제나 그렇듯 그 아이디어를 코드로 실현하는부분에서 생각보다 까다로웠던 문제다.

이문제 같은 경우는 굳이 from collections import deque 까지 사용하지 않고 그냥 배열로만 풀어도 되긴 하지만

문제가 너무 큐자료구조스러운 문제라 from collections import deque를 사용했다.

마지막으로 배열을 문자열로 바꾸거나 문자열을 배열로 바꾸는 부분은 어느 문제에서나 많이 활용되므로 꼭 알아두는것이 좋을 거 같다.!!