[알고리즘/C++] 백준 1158. 요세푸스 문제

요세푸스 순열은 여기서 그려볼 수 있다. Josephus Problem – GeoGebra

---

C++의 list STL로 풀고자 했던 문제. 처음 데이터를 저장하는 list와, 요세푸스 순열을 저장하는 list를 각각 선언 후, 저장 list를 하나씩 지워가며 순열 list로 옮기도록 코드를 작성했다.

그런데 list STL의 erase의 원리가 잘 이해되지 않아 한참을 헤메야 했다.
stl erase는 원소를 지운 후 다음 원소의 주소를 반환한다.
예를 들어 원소가 1,2,3,4일때 iterator가 3을 가리키는 상태에서 erase(iterator)를 하면, 원소는 3을 없애고 4를 가리킬 것이다.

이때 k번째 원소를 없앤다고 할 때 index i를 두고 나머지가 0이 되는 시점에 원소를 제거하게 했더니, index는 그대로인 채 원소만 제거되면서 코드가 생각한 대로 돌지 않는 문제가 발생해버렸다.

대략 이런...

이를 해결하고자, erase가 발생하는 시점에서는 iterator를 하나 이전으로 돌려주는 방식으로 코드를 작성했다.
이상한 점은, erase 후 iterator를 --해 주는 코드를 한 줄에 작성했더니 동작이 또 이상하게 나타난다. 함수 내부에서 동작하면서 원래 값을 수정하는 게 있는건지...

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

int main() {
	// your code goes here
	list<int> arr, ans;
	list<int>::iterator cur_arr;
	
	int n, k;
	cin >> n >> k;
	for(int i = 0 ; i < n ; i++){
		arr.push_back(i + 1);
	}
	int i = 1;
    cur_arr = arr.begin();
	while(!arr.empty()){
		if( i % k == 0){
			ans.push_back(*cur_arr);
			cur_arr = arr.erase(cur_arr);
			cur_arr--;
		}
		
		i++;
        cur_arr++;
        if(cur_arr == arr.end()) {
            cur_arr = arr.begin();
        }
	}
	list<int>::iterator c = ans.begin();
	cout << '<' << *c;
	for(c++ ; c != ans.end() ; c++){
		cout << ", " << *c;
	}
	cout << '>';
	return 0;
}