[ALGOSPOT] 조세푸스 문제

박민주·2021년 10월 2일
0
post-thumbnail

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;
}
profile
Game Programmer

0개의 댓글