https://www.algospot.com/judge/problem/read/JOSEPHUS
조세푸스 문제..
알고리즘 문제 해결 전략 2권의 18장에서 소개되는 문제이다!
18장은 선형 자료 구조를 다루고 있어서 이 문제 또한 선형 자료 구조를 쓰기에 적합하다
스케치
양방향 연결리스트까지는 쓰고 싶지 않아서
head랑 tail을 가리키는 포인터를 써야겠다고 생각했는데
C++에서 제공하는 리스트가 double linked list 라서
iterator를 사용하면 이전 노드로 돌아오는 것이 가능했다
선형 자료 구조에서는 동적배열과 연결리스트를 배웠는데,
조세푸스 문제 같은 경우에는 순회하면서 삭제해야 하니까
한 번 삭제할 때마다 원소의 대이동이 일어나는 동적배열보다는
포인터 연결만 바꿔주면 되는 연결리스트가 더 나을 거 같았다!
이 문제를 푸는데 유용하게 사용했던 C++ STL의 리스트 중 포인트라고 생각되는 점이 있다
1. erase(iter)를 사용하면 iterator가 가리키는 노드를 삭제할 수 있다
2. erase()로 삭제하면 자동으로 바로 다음 노드를 가리키게 된다
하지만 원형 연결리스트가 아니기 때문에
이동 중에 tail을 만나면 head로 돌아가도록 별도의 예외처리가 필요했다
CODE
#include <iostream>
#include <list>
using namespace std;
void PrintListAll(list<int> listt);
void SearchLastTwo(int N, int K);
int main(void)
{
int testcase = 0;
cin>>testcase;
int * input_N = new int[testcase];
int * input_K = new int[testcase];
for(int i=0; i<testcase; i++)
{
cin>>input_N[i]>>input_K[i];
}
for(int i=0; i<testcase; i++)
{
SearchLastTwo(input_N[i], input_K[i]);
}
delete[] input_N;
delete[] input_K;
return 0;
}
void SearchLastTwo(int N, int K)
{
list<int> josephus;
for(int i=0; i<N; i++)
{
josephus.push_back(i+1);
}
bool isEnd = false;
bool isFirst = false;
list<int>::iterator iter_main = josephus.begin();
for(iter_main = josephus.begin(); josephus.size() > 2;)
{
// 예외 1 : 지우려는 노드가 마지막 노드이면 삭제 후 iter을 end으로 옮겨주어야 함
if(iter_main == josephus.end())
{
isEnd = true;
}
// erase는 삭제 성공 시 삭제한 요소의 바로 다음 iterator를 return하기 때문에 그대로 대입
iter_main = josephus.erase(iter_main); /* 노드 삭제 */
if(isEnd)
{
iter_main = josephus.end();
isEnd = false;
}
// 예외 2: 삭제 후 노드가 마지막 노드이면 begin으로 옮겨주어야 함
if (iter_main == josephus.end())
{
iter_main = josephus.begin();
}
for(int i=0; i<K-1; i++) /* k-1만큼 이동 */
{
iter_main++;
// 예외 2 : 이동하다가 마지막 노드를 만나면 다시 처음으로 옮겨주어야 함
if(iter_main == josephus.end())
{
iter_main = josephus.begin();
}
}
}
PrintListAll(josephus);
josephus.clear();
}
void PrintListAll(list<int> listt)
{
list<int>::iterator iter;
for(iter = listt.begin(); iter != listt.end(); iter++)
{
cout<<*iter<<" ";
}
cout<<endl;
}