[Python/파이썬] 백준 알고리즘 1158번 - 요세푸스 문제

 

 

 

<풀이 1 - 성공>

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

circular_queue = [i for i in range(1, N+1)]
cursor = K-1
result = []
while circular_queue:
    result.append(str(circular_queue.pop(cursor)))
    # 순서 중요! N 감소가 cursor 이동보다 선행되어야 함.
    N -= 1
    if N > 0:
        if (cursor + K) % N == 0:
            cursor = N - 1
        else:
            cursor = (cursor + K) % N - 1

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

처음에 저 N -= 1을 뒷 순서에 놔서 애먹었다..

커서를 이동시켜가며 해당 인덱스에 도달했을때 pop해 result 리스트에 넣고 마지막에 출력하는 방식이다.

근데 구글링해보니 이것보다 훨씬 간결한 풀이가 있어 정리해보려고 한다.

 

<풀이 2 - 성공>

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

circular_queue = [i for i in range(1, N+1)]
cursor = 0
result = []
for _ in range(N):
    # 제거하면 인덱스가 앞으로 밀린다. 때문에 -1 해주기
    cursor += K-1
    # 한바퀴 돌고 다시 인덱스 0으로 오는 경우 고려
    cursor %= len(circular_queue)
    result.append(str(circular_queue.pop(cursor)))

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

생각해보니 N명의 사람을 제거하는데는 N번 횟수만큼만 시행하면 되는 것이었다.

그리고 복잡하게 생각할 것 없이 cursor의 값이 리스트의 인덱스 범위를 벗어나게 되는 것을 고려해 모듈러 연산으로 되돌려 놓으면 된다.

 

 

 

<핵심 정리>

1. Circular queue 구현 시 모듈러 연산을 이용해 인덱싱을 할 수 있다.

2. 리스트를 for문 없이 붙여서 출력하는 "".join(리스트) 의 경우 리스트의 element들이 문자열이어야 한다.