[algospot][JOSEPHUS] 조세푸스 문제

문제 : https://algospot.com/judge/problem/read/JOSEPHUS

---

N = 6, K = 3 을 예로 들어보자.

병사 리스트	삭제되는 인덱스 (0부터 시작)	삭제되는 병사 번호 (1부터 시작)
1 2 3 4 5 6	0	1
2 3 4 5 6	2	4
2 3 5 6	0	2
3 5 6	2	6

최종 결과는 위와 같다. 리스트에 병사들 번호를 차례대로 저장한뒤 배열요소가 2개가 남을 때까지 삭제되는 인덱스를 구해서 하나씩 배열에서 삭제시킨다.

삭제 인덱스는 0부터 시작하며 다음 삭제되는 인덱스는 삭제된 인덱스 + K -1 이다.

+K는 시계 방향으로 K 번째인 사람이 다음 삭제되는 인덱스이기 때문에 더해주었다.

-1은 현재 리스트에서 한 병사가 삭제되었기 때문에 이(삭제된 병사 인덱스 1)를 빼주어야 한다.

그리고 삭제된 배열의 크기를 나머지 연산해주어서 삭제되는 병사의 인덱스가 배열 크기를 넘어가는 경우를 방지한다.

즉, 삭제 인덱스 = (삭제 인덱스 + K - 1) % 배열 크기 로 갱신된다.

이를 배열 요소가 2개 남을 때까지 반복한다.

 

시간복잡도는 vector.erase 하는데 삭제된 이후 요소들을 앞으로 한 칸씩 움직이는 일도 하므로 O(N)이 소요된다.

여기서 N은 배열 길이인데 한 번 반복할 때마다 배열 길이가 1씩 줄어드니까 시간은 N + (N-1) + (N-2) + ... + 4 + 3 이다. (3까지인 이유는 2개가 남을때까지 반복하기 때문.) 따라서 대충 따져보면 시간복잡도는 O(N^2 / 2).

---

소스코드 : https://github.com/fpdjsns/Algorithm/blob/master/algospot/JOSEPHUS.cpp