백준 1158 요세푸스 문제 문제풀이

백준 #1158 요세푸스 문제입니다.

사람들이 원을 그리며 앉는 상황에서 문제는 매번 K번째 사람을 빼는 것이다.

선입 선출 데이터 구조 인 대기열을 사용하여 문제를 해결했습니다.

Python에서 액세스하고 사용할 수 있는 deque 데이터 구조를 사용했습니다.

deque 데이터 구조는 popleft()에서 pop()까지 O(1)에서 연산을 수행할 수 있는 데이터 구조입니다.

대기열을 통해 이 문제를 해결하려면 O(NK)의 시간 복잡도가 필요합니다.

내가 작성한 코드는 다음과 같습니다.

from collections import deque


def yosqp():
    for i in range(1, K + 1):
        temp = queue.popleft()
        if i != K:
            queue.append(temp)
        else:
            if queue:
                print(temp, end=", ")
            else:
                print(temp, end=">")


if __name__ == '__main__':
    N, K = map(int, input().split())
    queue = deque((i for i in range(1, N + 1)))
    print("<", end="")
    while queue:
        yosqp()