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

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

11866번: 요세푸스 문제 0

 

# 조건

• 1번부터 N번까지의 사람이 원을 이루며 앉아있고 양의 정수 K가 주어진다.
• K번째 사람을 제거하며 N명 모두가 제거 될 때까지 반복
• 제거되는 순서를 (N, K) - 요세푸스 순열이라고 한다.

 

# 접근 방법

• 큐의 성질을 이용하여 '줄 세우기와 같이' 앞에서 빼주고 K번째가 아니라면 다시 APPEND해준다.
• 출력 모양이 좀 이상해서 좀 당황했지만 자료구조를 떠올린다면, 어려운 문제는 아니였다고 생각한다.

 

N, K = map(int, input().split())  
  
arr = []  
# 순서대로 리스트로 만들어준다.
for i in range(1, N+1):  
    arr.append(i)  
  
  
cnt = 0  
result = []  
# 출력 모양에 맞춰 < 넣어주기
print('<', end='')  
# 모든 사람이 빠질 때까지
while arr:  
	# 첫 사람을 제외 시킨후 
    a = arr.pop(0)  
    cnt +=1  
    # K번째 사람이였다면 출력 리스트에 넣어 준후 카운트 초기화
    # K번째 사람이 아니었다면 다시 뒤에 줄세운다.
    if cnt == K:  
        result.append(a)  
        cnt = 0  
    else:  
        arr.append(a)  
# 출력에 맞춰 쉼표를 함께 넣어주다가 마지막 문자 출력시에는  >를 같이 넣어준다.
for i in result:  
    if not i == result[-1]:  
        print(i, end=', ')  
    else:  
        print(i, end='>')