1158 백준 요세푸스 문제 (파이썬)

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

1158번: 요세푸스 문제

나의 문제 분석

문제 자체는 이해하기 단순했다. 그냥 k번째 수를 계속 빼서 정답 배열에 넣어서 출력하면 되는 것이었다. 나는 덱을 사용하여서 왼쪽에서 k-1번째까지 빼고 뒤에 다시 넣고 k번째 뺀것은 answer 배열에 넣어서 n번 반복하였다. 그리고 answer를 출력해주었다. 

 

나의 해결 방안

#(n,k) - 요세푸스 순열
from collections import deque
n,k = map(int,input().split())
answer = []
q1=deque([])
for i in range(n):
    q1.append(i+1)
for _ in range(n):
    for _ in range(k-1):
        num = q1.popleft()
        q1.append(num)
    num = q1.popleft()
    answer.append(num)
print("<",end='')
for i in range(n-1):
    print(answer[i],end=', ')
print(answer[n-1],end='>')

중간중간 deque의 사용방법이 걸려서 찾아보면서 해결하였다.

 

다른 사람 풀이

사실 deque로 푸는 것보다 queue로 푼 해설을 찾아보고 싶었다. 파이썬에서는 list자체가 queue이기 때문에 간단하게 풀 수 있을 거라고 생각했다. 

아래 풀이를 참고했다.

https://infinitt.tistory.com/213

백준 (boj) 파이썬 - 1158 요세푸스 문제

여기서는 arr을 처음에 앉아있는 사람들 배열로 저장해주었고 제거될 사람을 num 변수로 계산하였다. 내가 처음에 고민했던 부분은 나중에 k보다 사람이 적었을때 한바퀴 돌고 다시 돌아와야된다는 점을 어떻게 해결할지 고민이였다. 

여기서는 num이 arr의 길이보다 크면 num = num % len(arr)을 통해서 num의 값을 맞춰주었다.