[BOJ] 1158: 요세푸스 문제

문제: https://www.acmicpc.net/problem/1158

 

 

 

 

#include <bits/stdc++.h>
using namespace std;
list<int> perm;
vector<int> result;
int n, k;
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> k;
  for (int i = 1; i <= n; i++) perm.push_back(i);
  for (list<int>::iterator addr = perm.begin(); perm.empty() != true;) {
    for (int i = 0; i < k - 1; i++) {
      addr++;
      if (addr == perm.end()) addr = perm.begin();
    }
    result.push_back(*addr);
    if ((addr = perm.erase(addr)) == perm.end()) addr = perm.begin();
  }
  cout << '<';
  for (int i = 0; i < result.size() - 1; i++) cout << result[i] << ", ";
  cout << result[result.size() - 1] << '>' << '\n';
}

k간격으로 임의의 위치에 있는 원소들을 제거하기 위해 연결리스트를 사용해서 해결했다.

연결리스트 perm을 선언하고, 1부터 n까지 push한다.

이제 perm이 empty가 될 때까지 k간격만큼 떨어진 위치에 있는 요소를 반복적으로 제거해야 한다.

더 정확히는 현 위치에서 k번째에 있는 원소를 가리키는 것이기 때문에 k-1 간격만큼 떨어진 원소를 삭제한다고 보면 된다.

따라서 perm의 iterator를 begin으로 초기화한 후 k-1번만큼 증가시켜서 연결리스트를 순회했다.

이때 addr이 연결리스트를 계속 순환하게 하기 위해서 end를 가리키면 begin으로 재할당 해야한다.

다음으로 addr이 가리키는 원소를 result에 push하고, addr은 다음 원소를 가리키면 된다.

여기도 마찬가지로 addr이 end를 가리키면 begin으로 재할당해야 한다.