- 문제 (1158번) : 요세푸스 문제
- 사람의 수 N과 사람을 없앨 위치 K를 입력받았을 때 (N, K)-요세푸스 순열을 출력하는 문제
- 입력 및 출력
[입력]
- 첫째줄에 사람의 수 N과 사람을 없앨 위치 K를 빈칸을 사이에 두고 입력
[출력]
- 아래의 형태로 요세푸스 순열 출력
(형식 : <숫자, 숫자, 숫자, ..., 숫자>)
- 문제 풀이
- 일반 queue를 사용하되, 원형 queue로 생각해 해결한다.
(front 원소 pop -> queue에 다시 push 하게 되면 원형처럼 작동한다.)
- 1부터 입력받은 N까지 queue에 넣는다.
- queue 내에서 입력받은 K에 -1한만큼만 front원소를 pop하고 다시 queue에 넣는다. (원형으로 도는것처럼 보임.)
- 2번을 끝낸 후 front에 있는 원소를 pop해 결과를 저장하는 배열에 저장.
- 2, 3번을 1에서 만든 queue가 빌 때까지 수행
(while(!queue.empty()) 로 반복)
- 위의 과정에서 결과값들을 저장한 배열의 원소를 형식에 맞춰 출력
- 최종 코드
