[백준] 1158. 요세푸스 문제 - Python

[Silver IV]

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

1158번: 요세푸스 문제

풀이

<풀이 1>

1~n 까지 수가 담겨있는 numberList를 n회 반복하며 index를 계산하여 요세푸스 순열에 값을 넣어준다.

numberList의 길이만큼 반복하므로 시간복잡도는 O(n)이 된다.

n, k = map(int, input().split())



numberList = [i for i in range(1, n + 1)]

josephusPermutation = []



index = 0

for i in range(len(numberList)):

    index = (index + k - 1) % len(numberList)

    josephusPermutation.append(str(numberList[index]))

    numberList.pop(index)



# print('<', end="")

# for i in range(len(josephusPermutation)):

#     if i == len(josephusPermutation) - 1:

#         print(josephusPermutation[i], end="")

#     else:

#         print(josephusPermutation[i], end=", ")

# print('>')

print("<",", ".join(josephusPermutation)[:],">", sep='')

<풀이 2>

queue에서 k 번째마다 front에서 rear로 값을 이동시키며 queue의 값이 모두 없어질 때까지 반복하는

풀이를 생각했지만, queue.pop(0)의 시간복잡도는 O(n)이다.

이 과정을 n개의 수에 대하여 k번 반복하면 전체 시간복잡도는 O(kn^2)가 된다.

혹시 몰라 코드를 구현해보니 역시나 시간초과가 떴다.

deque을 사용하여 deque.popleft()를 사용하면 시간복잡도는 O(1)로 줄어들었다.

위와 동일한 과정을 반복하면 전체 시간복잡도는 O(kn)가 된다.

from collections import deque

n, k = map(int, input().split())



numberList = deque([i for i in range(1, n + 1)])

josephusPermutation = []



while numberList:

    for i in range(k - 1):

        numberList.append(numberList.popleft())

    josephusPermutation.append(str(numberList.popleft()))



# print('<', end="")

# for i in range(len(josephusPermutation)):

#     if i == len(josephusPermutation) - 1:

#         print(josephusPermutation[i], end="")

#     else:

#         print(josephusPermutation[i], end=", ")

# print('>')

print("<",", ".join(josephusPermutation)[:],">", sep='')

주의할 점

처음에 값은 잘 나왔지만 계속 틀렸다. 왜 그런지 모르겠지만, 요세푸스 순열을 int형으로 출력하니 에러가 나는 것 같았다.

문자열로 형변환을 해주고 출력하니 결과값이 잘 나왔다. 또한, print("", sep='')를 통해 출력 형식을 맞추면 보다 간결하게

코드를 구현할 수 있었다.