[Python] 백준 11866번: 요세푸스 문제 0

Jonie Kwon·2022년 4월 17일
0

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

풀이

  1. deque.rotate 사용
    deque의 rotate 함수를 이용하면 n만큼 왼쪽(-n) 오른쪽(+n)으로 리스트를 이동시킬 수 있다.
    이를 이용해서 k번째의 숫자를 가장 앞으로 이동시켜서 왼쪽부터 차례로 빼도록 구현하였다

  2. deque 사용하지 않고
    deque로 구현하고 끝내기에는 뭔가 공부한 것 같지가 않아서 쓰지 않고 구현해보았다.
    k번째의 숫자를 하나씩 빼면 인덱스도 하나씩 줄어 들기 때문에 k를 더한 후 1를 빼준다.
    인덱스의 범위가 벗어나지 않도록 리스트의 전체 길이로 나눈 값을 사용한다. 20ms 단축

코드

deque.rotate 사용

import sys
from collections import deque
input = sys.stdin.readline
n, k = map(int,input().split())
circle = deque([x for x in range(1,n+1)])
removed = []
while circle:
    circle.rotate(-(k-1))
    removed.append(circle.popleft())
print(f'<{", ".join(map(str,removed))}>')

deque 사용하지 않고

import sys
input = sys.stdin.readline
n, k = map(int,input().split())
circle = [x for x in range(1,n+1)]
removed = []
now = k-1
while circle:
    removed.append(circle.pop(now))
    if circle:
        now = ((now-1) + k) % len(circle)
print(f'<{", ".join(map(str,removed))}>')

profile
메모하는 습관

0개의 댓글