[백준/C++] 1158번 요세푸스 문제

1158번 요세푸스 문제

문제

요세푸스 문제는 다음과 같다.

1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 <3, 6, 2, 7, 5, 1, 4>이다.

N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

출력

예제와 같이 요세푸스 순열을 출력한다.

풀이

큐 queue

큐는 FIFO 동작을 한다. 즉, 먼저 들어온 값이 먼저 나간다. 이를 이용해 k-1번째까진 맨 앞의 값을 빼서 맨 뒤에 다시 넣고, k번째에는 맨 앞의 값을 제거한다. 이를 큐가 빌 때까지 반복한다.

1. 큐에 1부터 n까지의 정수를 삽입한다. (큐 초기화)
2. 큐의 맨 앞의 값을 맨 뒤에 다시 삽입하고 맨 앞의 요소를 삭제한다. 이를 k-1 번 반복한다.
3. 현재 큐의 맨 앞의 요소를 출력하고, 이를 삭제한다. 이 동작이 k 번째 사람을 제거하는 것이다.
4. 현재 큐가 비어있다면 남아있는 사람이 없다는 의미이다. 따라서 '>'를출력한다. 큐가 비어있지 않으면 ", "를 출력한다.
5. 큐가 비어 있을 때까지 2~4의 동작을 반복한다.

연결리스트 linked list

C++ STL의 list는 이중 연결 리스트이다. 그러므로 iterator의 증가, 감소 연산을 통해 이전, 다음 노드에 접근할 수 있다.

1. 리스트에 1부터 n까지 정수를 추가한다.(리스트 초기화)
2. iter를 k번 증가시킨다. 이때 iter가 리스트의 마지막 요소의 다음에 추가될 위치를 가리키고 있다면 iter를 리스트의 맨 처음으로 초기화한다.
3. iter가 가리키고 있는 위치의 값을 출력한다.
4. iter가 가리키고 있는 위치의 값을 삭제한다. 이때 erase 함수는 삭제된 노드가 가리키는 다음 주소의 위치를 가리킨다. 그러므로 iter를 1 감소시켜 이전 노드의 위치를 가리키도록 한다.
5. 현재 리스트가 비어있다면 남아있는 사람이 없다는 의미이므로 '>'를 출력한다. 리스트가 비어있지 않으면 ", "를 출력한다.
6. 리스트가 비어있을 때까지 2~5의 동작을 반복한다.

코드

Queue

#include <iostream>
#include <queue>
using namespace std;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  cin >> n >> k;

  queue<int> q;

  cout << '<';
  for (int i = 1; i <= n; i++)
    q.push(i);

  while (!q.empty()){
    for (int i = 0; i < k - 1; i++){
      q.push(q.front());
      q.pop();
    }
    cout << q.front();
    q.pop();

    if (q.empty()) cout << '>';
    else cout << ", ";
  }
  return 0;
}

list

#include <iostream>
#include <list>
using namespace std;

int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  cin >> n >> k;

  list<int> lis;
  list<int>::iterator iter = lis.begin();

  cout << '<';
  for (int i = 1; i <= n; i++)
    lis.push_back(i);

  while (!lis.empty()){
    for (int i = 0; i < k; i++){
      if (++iter == lis.end())
        iter = lis.begin();
    }
    cout << *iter;
    iter = --lis.erase(iter);

    if (lis.empty()) cout << '>';
    else cout << ", ";
  }
  return 0;
}