[Baekjoon] 백준 알고리즘: 11866 - 요세푸스 문제 0

문제

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

11866번: 요세푸스 문제 0

내가 생각했던 풀이과정

 

1. K번째 사람을 제거하고, 남은 사람들로 이루어진 원을 따라 계속한다는 점은 원하는 요소를 pop할 수 있게 회전 한 후 pop한다고 생각을 하여 deque를 이용하였다.

2. 원하는 요소를 pop하기 위해 -(K-1) 만큼 회전을 한다. -(K-1) 만큼 회전하는 이유는 좌로 회전하기 위함이다

3. 좌로 회전을 하고 맨 처음 요소를 popleft 한 것을 리스트에 넣는다. 리스트에 넣을 때는 < >안에 넣어야하기 때문에 문자열로 처리해서 넣는다.

4. 문자열로 각 요소를 출력한다.

 

나의 풀이

from collections import deque

queue = deque()
N, K = map(int, input().split())

result = []
for i in range(N): 
    queue.append(i + 1) 

for j in range(N):
    queue.rotate(-(K-1))
    result.append(str(queue.popleft()))

print("<%s>" %(", ".join(result)))

다른 사람의 풀이

N, K = map(int, input().split()) 
circular_list = [] 
answer = []
for i in range(N): circular_list.append(i+1) 
popNum = 0 

while len(circular_list) > 0:
    popNum = (popNum + (K-1)) % len(circular_list) 
    popElemnet = circular_list.pop(popNum) 
    answer.append(str(popElemnet)) 
    
print("<%s>" %(", ".join(answer)))

pop 자체를 이용하기 위해 popNum에 K - 1을 더하고 길이만큼 나누는 방식으로 로직을 구성하면 똑같이 구할 수 있다.

새로 알게된 점, 확인해야할 점