BOJ 11866 - 요세푸스 문제 [Python]

11866번: 요세푸스 문제 0 (acmicpc.net)

11866번: 요세푸스 문제 0

백준 11866번 문제로, 문제 설명은 아래와 같다.

문제 설명

아래는 입력과 출력 예시이다.

입력과 출력 예시

 

 우선 내가 사용한 사고 방식은 다음과 같다.

 

 1. 리스트에 n개의 원소를 다 넣는다.

 2. k 번째 애를 빼야 하니, 첫 index를 k-1로 놓는다.

 3. 그 애를 pop하고, index 값을 k-1을 더해 다음 애를 가리키게 한다.

 4. 이 때 index의 값이 list의 원소 개수를 넘어갔다면, 그 원소 개수만큼 빼줘서 다시 앞쪽으로 가게 한다.

 5. 리스트 안의 n개의 값들이 모두 pop 될 때 까지 반복한다.

 

Queue와 같은 자료구조를 안쓰게 구현하려고 하다보니, 조금 요상하지만 잘 굴러가는 코드를 작성할 수 있었다 :)

 

아래는 제출한 파이썬 코드이다.

 

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

anslist = []
for idx in range(1,n+1):
    anslist.append(idx)

idx = k-1
aa = []
while len(anslist)!=1:
    while idx >= len(anslist):
        idx -= len(anslist)
    aa.append(anslist.pop(idx))    
    idx += k-1
aa.append(anslist.pop())
ans = "<"
for j in range(len(aa)):
    if j == len(aa)-1:
        ans += str(aa[j])+">"
    else:
        ans += str(aa[j])+", "
print(ans)