조세푸스(josephus) 알고리즘 정리

조세푸스(Josephus)알고리즘 (종만북2 P.622)

list객체.begin()은 주소의 처음
list객체.end()은 (마지막원소의 주소 +1)인 리스트 size를 반환한다.
list객체.erase(A)는 A를 지운 뒤, (A의 다음원소)를 반환
.front()는 첫번째 원소 | .back()은 마지막 원소

2시간동안 헤매던 것 정리.

if(kill==survivors.end()) kill=survivors.begin();
이 부분에 대해 이해를 못함

survivors.end은 마지막원소의 데이터가 아닌, 리스트의 전체 크기를 말한다
따라서, 1과 4가 죽었을때 survivors.end()는 남은 인원수인 4를 말하며
kill의4는 몇번째 사람인지를 말한다.

kill==survivors.end()일때 kill=survivors.begin()을 한 이유는
이때 kill은 사이즈를 나타내므로 erase를 한다고해서 다음원소를 나타내는게 아니라 리스트사이즈를 나타낸다.
따라서 survivors.begin()을 해줘야 원형리스트로 작동

주소에는 리스트가 ( {1,2,3,4,5,6}과 {{LIST_SIZE}} ) 로 구성되어있음

---

내가 오해한 사항
-> survivors.begin()은 ++kill 을 해버린 셈아닌가?
=> survivors.end()는 리스트의 크기를 나타내므로 원소값을 가르키는게 아니다.
마지막원소의 다음주소값은 리스트크기이므로, 내가 의도하는 마지막원소의 다음차례를 가르키려면 마지막이 아닌원소의 kill+=2를 해야하나 리스트자체가 원형리스트는 아니기에, 마지막원소이자 리스트의 마지막 주소값에서 begin()으로 와야한다.
대략 요약하자면 마지막원소의 다음값은 다른원소랑은 다름. 리스트의 크기를 가르킨다.

#include <iostream>
#include <list>

using namespace std;

void josephus(int n,int k){
    list<int> survivors;
    for(int i=1;i<=n;++i) {
        survivors.push_back(i);
    }
    list<int>::iterator kill = survivors.begin();
    while(n>2)
    {
        cout<<"kill who? : "<<*kill<<endl;
        kill=survivors.erase(kill);
        //마지막이 아닌걸 죽일때는 다음원소(데이터인 값)이 반환되지만
        // 마지막을 죽였을때 다음값은 전체사이즈이다.
        // 따라서 kill이 마지막을 가르키면 처음값으로 돌려놔야 원형리스트로 동작한다.
        if(kill==survivors.end())
        {
            cout<<"survivors.end : "<<*kill<<endl;
            kill=survivors.begin();
            cout<<"survivors.begin : "<<*kill<<endl;
        }
        --n;

        for(int i=0;i<k-1;++i)
        {
            cout<<*kill<<endl;
            ++kill;

            if(kill==survivors.end()) {
                //cout<<"Survival : "<< survivors<<endl;
                cout<<"what is survivors.end : "<<*survivors.end()<<endl;
                cout<<"in for, survivors.end : "<<*kill<<endl;
                kill = survivors.begin();
                cout<<"in for, survivors begin : "<<*kill<<endl;
            }
        }
    }
    cout<<survivors.front()<<' '<<survivors.back()<<endl;

}

int main()
{
    josephus(6,3);
}

실행결과

kill who? : 1
2
3
kill who? : 4
5
6
what is survivors.end : 4
in for, survivors.end : 4
in for, survivors begin : 2
kill who? : 2
3
5
kill who? : 6
survivors.end : 2
survivors.begin : 3
3
5
what is survivors.end : 2
in for, survivors.end : 2
in for, survivors begin : 3
3 5