백준 - 11866(요세푸스 문제0) C++

https://www.acmicpc.net/problem/11866

11866번: 요세푸스 문제 0

N이 주어지면 1부터 N까지 오름차순으로 원을 그려 앉고 오름차순으로 K번째 해당하는 수를 모든 수가 삭제될 때까지 반복해서 지우며 그 순서를 출력하는 문제이다.

 

예를 들어, N = 7, K = 3이다.

1) 1, 2, 3 -> 3 삭제 => 1, 2, 4, 5, 6, 7

2) 4, 5, 6 -> 6 삭제 => 1, 2, 4, 5, 7

3) 7, 1, 2 -> 2 삭제 => 1, 4, 5, 7

4) 4, 5, 7 -> 7 삭제 => 1, 4, 5

5) 1, 4, 5 -> 5 삭제 => 1, 4

6) 1, 4, 1 -> 1 삭제 => 4

7) 4 

그래서 답은 <3, 6, 2, 7, 5, 1, 4>이다.

 

이 방법을 큐(queue)와 벡터(vector)를 이용해서 풀었다.

큐는 처음 데이터를 입력받고 K만큼 빼고 다시 넣는 걸 반복하는 용도로, 벡터는 마지막 K번째 빼는 데이터를 저장할 용도로 사용했다.

 

k - 1번 동안 큐에 가장 앞에 있는 데이터를 빼고 다시 큐의 뒤로 넣는 작업을 반복한다.

k번째 데이터는 빼서 큐가 아닌 스택에 저장한다.

for (int i = 0; i < k-1; i++){
      top = q.front();
      q.pop();
      q.push(top);
    }
    top = q.front();
    q.pop();
    vec.push_back(top);
    N++;

 

위의 작업을 n - 1번 반복한다.

참고로 코드에서는 n이 입력되는 데이터의 수이고 N이 n의 횟수만큼 실행되도록 설정한 변수이다.

그래서 N = 0부터 시작해 n - 1일 때까지 즉, 마지막 데이터가 하나 남을 때까지 반복한다.

int N = 0;
  vector<int>vec;
  while (N < n)
  {
    int top;
    for (int i = 0; i < k-1; i++){
      top = q.front();
      q.pop();
      q.push(top);
    }
    top = q.front();
    q.pop();
    vec.push_back(top);
    N++;
  }

결과 코드는 아래와 같다.

#include <stdio.h>
#include <queue>
#include <vector>
using namespace std;

int main(){
  int n, k;
  scanf("%d %d", &n, &k);
  queue<int>q;
  for (int i = 1; i <= n; i++)
    q.push(i);

  int N = 0;
  vector<int>vec;

  // 데이터가 1개 남을 때까지 반복
  while (N < n)
  {
    int top;
    // k-1번 데이터를 빼고 넣고 반복
    for (int i = 0; i < k-1; i++){
      top = q.front();
      q.pop();
      q.push(top);
    }
    // k번째 데이터는 다시 넣지 않고 벡터에 저장
    top = q.front();
    q.pop();
    vec.push_back(top);
    N++;
  }
  printf("<");
  for (int i = 0; i < vec.size()-1; i++)
  {
    printf("%d, ", vec[i]);
  }
  // 마지막 남은 데이터
  printf("%d", vec[vec.size()-1]);
  printf(">\n");
    
  return 0;
}

실행 결과