백준 #1158 요세푸스

1158번: 요세푸스 문제 (acmicpc.net)

1158번: 요세푸스 문제

 

파이썬 코드.

n, k = map(int,input().split())
arr=[]
size=n
queue = []
for i in range(1,n+1):
    arr.append(i)
front = rear = -1

print('<',end='')

for i in range(n):
    for _ in range(k):
        a=(front+1)%size
        front=a
    print(arr[a], end='')
    if i<n-1:
        print(', ', end='')
           
    rear = front-1
    del arr[front]
    size-=1
    front=rear
   
print('>')

 

deque를 안 쓰고 그냥 원형 queue에서 front랑 rear를 조절하는.. 자료구조 책에 나온 방법으로 풀었던 것 같다. 

 

 

 

2024년 9월에 다시 푼 방법: 위의 풀이보다 시간이 몇십배 단축됨.

#요세푸스 문제
from collections import deque

n, k = map(int, input().split())
arr=deque([i for i in range(1, n+1)])

yosep = []

while len(arr)>0:
    arr.rotate(-(k-1))
    yosep.append(arr.popleft())

print("<" + ", ".join(map(str, yosep))+ ">")

 

#

rotate할 때 양수는 오른쪽으로 미는 거, 음수는 왼쪽으로 미는 거. 직관적으로 왠지 그럴 것 같은 방향임.


#

join이라는 게 있음. 이게 뭐냐면 리스트에 있는 각각의 원소들을 한번에 출력할 수 있게 해주는 메서드인데
join앞에다가 구분자를 쓸 수 있음. 이 경우에는 출력을 쉼표를 넣어서 하면 됨.
그리고 원래 이 기능은 문자열이 원소일 때만 사용 가능하므로 지금은 map이용해서 숫자를 문자열로 바꾼 다음에 출력해야 함.