[파이썬] 백준 11866 : 요세푸스 문제 0

[파이썬] 백준 11866 : 요세푸스 문제 0

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

11866번: 요세푸스 문제 0

실버 4

구현, 자료구조, 큐

---

1~N번까지의 리스트를 K번째 마다 건너뛰면서 순회하며 제거해야 한다.

인덱스 값이 K를 넘어갈 때와, 리스트 값이 제거될 때 인덱스 값을 어떻게 주어야 하는지 유의하며 풀었다.

 

코드(68ms)

import sys
input = sys.stdin.readline
N, K = map(int, input().split())
yose = [i for i in range(1, N+1)]
idx = K - 1
slst = []
print('<', end='')
while yose:
    if idx < len(yose):
        slst.append(yose[idx])    # 제거 예약
        idx += K
    
    else:
        idx -= len(yose)
        for i in slst:
            yose.remove(i)
            print(i, end='')
            if yose:
                print(', ', end='')
        slst.clear()
print('>')

 

yose를 1~N까지의 값을 담은 리스트로 삼았다.

idx값이 K만큼 건너뛰다가 리스트의 범위를 벗어나면 리스트의 길이만큼 idx값을 빼줌으로써 인덱스 값을 조절했다.

 

또한, 제거 대상이 되는 수를 slst 리스트에 넣어 제거 예약을 걸어두고,

idx값이 리스트 범위를 벗어날 때 slst에 있는 값을 다시 불러와 기존의 yose의 값과 같은 것을 전부 제거했다.

만약 idx값이 지나가면서 값을 바로 지워버리면 리스트의 범위가 계속 변하기 때문에 원하는 인덱스 값을 찾을 수 없게 된다.

 

yose리스트에 값이 있으면 slst에 담아두었던 값들을 하나씩 , 로 구분하여 출력하고, yose리스트의 값이 하나도 없으면 반복문을 빠져나와 >를 출력한다.

 

 

 

큐를 이용한 다른 사람 코드(128ms)

from collections import deque

queue = deque()
answer = []

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

for i in range(1, n+1):
    queue.append(i)

while queue:
    for i in range(k-1):
        queue.append(queue.popleft())
    answer.append(queue.popleft())

print("<",end='')
for i in range(len(answer)-1):
    print("%d, "%answer[i], end='')
print(answer[-1], end='')
print(">")

1~N까지의 수를 덱으로 선언한 queue에 담는다.

K값만큼 건너뛰면서 제거할 수를 선택하므로 K-1까지의 수를 큐에서 제거했다가 큐의 마지막 인덱스에 다시 추가한다.

그리고 K번째에 있는 수는 제거한 뒤 answer리스트에 추가한다.

 

문제 양식에 맞게 출력하기 위해 리스트의 마지막 값을 제외하고 ,를 붙여 출력하도록 하였고,

마지막 숫자는 , 없이 출력하도록 구별시켰다.