[Algospot] 선형자료구조 / JOSEPHUS / Python 파이썬

[Algospot] 선형자료구조 / JOSEPHUS / Python 파이썬

[Algospot] 비트마스크 / GRADUATION / Python 파이썬

 

풀이

원형 큐를 구현하는 문제이다.

모든 병사의 생사여부 정보를 원형 큐로 구현하여 index 로 조회하였더니 시간초과가 발생하였다.

 

모든 병사의 정보가 아닌 생존한 병사의 정보만 저장하고, 사망한 병사의 정보는 array 에서 삭제시켜 전체 array 크기를 줄여
매 시행마다 전체 시간을 축소 시키는 방법이 유효한 전략이다.

 

간단하지만 간단하지 않은 문제였다.

 

 

C = int(input())

for _ in range(C):
    N, K = map(int, input().split())

    alive = [x+1 for x in range(N)]
    kill = 0
    while len(alive) > 2:
        del alive[kill]
        kill = (kill+K-1) % len(alive)

    print(*alive)  # print(" ".join(map(str, alive)))