[C++] 백준 1158번 풀이 (요세푸스 문제)

정민경·2023년 1월 9일
0

baekjoon

목록 보기
10/57
post-thumbnail

- 문제 (1158번) : 요세푸스 문제

  • 사람의 수 N과 사람을 없앨 위치 K를 입력받았을 때 (N, K)-요세푸스 순열을 출력하는 문제

- 입력 및 출력

[입력]

  • 첫째줄에 사람의 수 N과 사람을 없앨 위치 K를 빈칸을 사이에 두고 입력

[출력]

  • 아래의 형태로 요세푸스 순열 출력
    (형식 : <숫자, 숫자, 숫자, ..., 숫자>)

- 문제 풀이

  • 일반 queue를 사용하되, 원형 queue로 생각해 해결한다.
    (front 원소 pop -> queue에 다시 push 하게 되면 원형처럼 작동한다.)

  1. 1부터 입력받은 N까지 queue에 넣는다.
  1. queue 내에서 입력받은 K에 -1한만큼만 front원소를 pop하고 다시 queue에 넣는다. (원형으로 도는것처럼 보임.)
  1. 2번을 끝낸 후 front에 있는 원소를 pop해 결과를 저장하는 배열에 저장.
  • 2, 3번을 1에서 만든 queue가 빌 때까지 수행
    (while(!queue.empty()) 로 반복)
  1. 위의 과정에서 결과값들을 저장한 배열의 원소를 형식에 맞춰 출력

- 최종 코드

0개의 댓글