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

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

 

 

사용 알고리즘: 덱

 

 

입력

• 첫째 줄에 N 과 K 가 빈 칸을 사이에 두고 순서대로 주어짐 (1 <= K <= N <= 1000)

 

 

1 번부터 N 번까지 N 명의 사람이 원을 이루며 앉아있을 때, N 명의 사람이 모두 제거될 때까지 K 번째 사람을 제거해 나감.

-> 앞 뒤로 추가/제거가 가능한 덱을 사용해서 원처럼 동작하도록 구현

 

입력이 7 3 인 경우,

1 2 3 4 5 6 7 의 숫자를 가진 사람들이 원을 그리며 앉아 있을 때, 3 번째 사람을 계속해서 제거해 나가야 한다.

 

- 1 을 제거하고 다시 뒤에 붙임 

2 3 4 5 6 7 1

 

- 2를 제거하고 다시 뒤에 붙임

3 4 5 6 7 1 2

 

- 3을 제거 (K = 3)

4 5 6 7 1 2

 

 

for 문을 돌면서 K 번째 사람을 제거해 나감. 

d = deque(x for x in range(1, N+1)) # 덱에 1~N 번을 미리 넣어둠

results = [] # 결과를 넣을 배열

for i in range(N):
    for j in range(K):
        if j == K-1: # j == K 일 땐 제거만 함
            results.append(d.popleft())
        else: # 그 외엔 제거하고 다시 추가
            d.append(d.popleft())

 

 

출력 형식을 지켜 출력함.

print('<', end='')
for i in range(N):
    if i == N-1:
        print(results[i], end='')
    else:
        print(results[i], end=', ')
print('>')

 

 

 

전체 코드

from collections import deque
import sys
input = sys.stdin.readline

# 입력
N, K = map(int, input().split())

d = deque(x for x in range(1, N+1)) # 덱에 1~N 번을 미리 넣어둠

results = [] # 결과를 넣을 배열

for i in range(N):
    for j in range(K):
        if j == K-1: # j == K 일 땐 제거만 함
            results.append(d.popleft())
        else: # 그 외엔 제거하고 다시 추가
            d.append(d.popleft())
# 출력
for i in range(N):
    if i == N-1:
        print(results[i], end='')
    else:
        print(results[i], end=', ')
print('>')

 

 

 

시간 복잡도

 

- 입력

N, K = map(int, input().split()) # O(1)

 

- K 번째 사람 제거하는 부분

 

popleft / append: O(1)

 

안쪽 for 문은 K 번을 돌고, 바깥쪽 for 문은 N 번을 돌기 때문에 O(K * N) = O(NK) 의 시간 복잡도를 가짐. 

d = deque(x for x in range(1, N+1)) # O(N)

results = []
for i in range(N):
    for j in range(K):
        if j == K-1:
            results.append(d.popleft())
        else:
            d.append(d.popleft())
            
# O(N) + O(N * K) = O(NK)

 

- 출력

print('<', end='')
for i in range(N):
    if i == N-1:
        print(results[i], end='')
    else:
        print(results[i], end=', ')
print('>')

# O(N)

 

 

그래서 총 시간 복잡도는 O(1) + O(NK) + O(N) = O(NK) 이다.

 

- 입력: O(1)

- K 번째 사람 제거하는 부분: O(NK)

- 출력: O(N)