[BOJ] 1158: 요세푸스 문제

🔒 예제

>> 7 3

<3, 6, 2, 7, 5, 1, 4>

🔧 풀이

1. n, k = map(int, sys.stdin.readline().split())
2. 순환하는 큐 c, result = []
	2.1 풀이 a : i가 순환하며 증가
    	    1) result.append(c[i])
    	    2) c.remove(i)
    	    3) i += (k-1) 
	2.2 풀이 b : 값들이 순환하며 이동
    	    1)tmp = c[0]
    	    2) c.pop()
    	    3) if cnt == k: print(tmp), cnt = 1

🔑 답안

import sys
from collections import deque

n, k = map(int, sys.stdin.readline().split())
result = []
c = deque([i for i in range(1, n+1)])

# 풀이 a -----------------------------------
i = 0
while len(c) > 0:
    i += (k - 1)
    if i >= len(c):
        i = i % len(c)
    result.append(str(c[i]))
    c.remove(c[i])
    
# 풀이 b -----------------------------------
cnt = 1
while len(c) > 1:
    tmp = c[0]
    c.popleft()
    
    if cnt == k:
        result.append(str(tmp))
        cnt = 1
    else:
        c.append(tmp)
        cnt += 1

result.append(str(c[0]))
# ---------------------------------------

print("<" + ", ".join(result) + ">")

💡 개념

좋은 웹페이지 즐겨찾기