[BOJ] 1158번 조세퍼스 문제

조세퍼스 문제 링크

어떻게 풀까?

해당 문제는 환형 링크드 리스트를 이용했습니다.

환형 링크드 리스트란?!

처음과 끝이 연결되어있는 링크드 리스트입니다!

환형 링크드 리스트는 보통 링크드 리스트와는 조금 다르게 head가 없습니다!

왜냐하면, 어짜피 끝과 처음이 연결되어 있기 때문입니다! tail의 바로 다음이 head가 되겠죠!

해당 문제는 환형큐를 만들기만 하면 아주 쉽게 해결됩니다.

m칸 옮긴 다음에 해당 칸을 삭제후 출력하는 것을 n번 반복하면 되기 때문이죠!

예제를 풀어보면,

처음에 리스트에는 1,2,3,4,5,6,7 이 들어있습니다!

그리고 커서를 3번 옮겨줍니다.

그러면 3에서 커서가 멈추게 됩니다!

3을 출력후 삭제합니다!

출력 : 3

환형 리스트 : 1,2,4,5,6,7

커서 : 2

또다시 커서를 3번 옮겨줍니다.

커서가 4와 5를 거쳐 6에서 멈춥니다.

그러면, 리스트에서 6을 출력 후 삭제합니다.

출력 : 3 6

환형 리스트 : 1,2,4,5,7

커서 : 5

커서를 3번 옮깁니다.

7을 거쳐 1로 돌아옵니다! 그리고 2에 멈추게 됩니다.

그러면 2를 출력 후 삭제합니다.

출력 : 3 6 2

환형 리스트 : 1,4,5,7

커서 : 1

커서를 3번 옮깁니다.

4에서 5를 거쳐 7에서 커서가 멈춥니다.

7을 출력 후 삭제합니다.

출력 : 3 6 2 7

환형 리스트 : 1,4,5

커서 : 5

커서가 1로 돌아와서 4를 거쳐 5에 위치합니다.

5를 출력 후 삭제합니다.

출력 : 3 6 2 7 5

환형 리스트 : 1,4

커서 : 4

커서가 1, 4를 거쳐 다시 1에 위치합니다.

1을 출력 후 삭제합니다.

출력 : 3 6 2 7 5 1

환형 리스트 : 4

커서 : 4

이제 몇번을 커서를 움직여도 커서는 4에 위치합니다.

4를 출력합니다.

출력 : 3 6 2 7 5 1 4

그러면 예제와 같은 순열이 출력됩니다!

코드

#pragma once
#include<cstdio>
 
struct NODE
{
    int value;
    NODE *next, *prev;
 
    NODE()
    {
        prev = next = 0;
    }
};
 
static struct MYMAL
{
    int idx;
    NODE nodes[5002];
 
    MYMAL()
    {
        idx = 0;
    }
 
    NODE* malloc()
    {
        return &nodes[idx++];
    }
} mymal;
 
struct LIST
{
    NODE *tail, *cursor;
    LIST()
    {
        tail = 0;
    }
 
    void insert(int i)
    {
        NODE* nn = mymal.malloc();
        nn->value = i;
 
        if (tail) {
            nn->next = tail->next;
            nn->next->prev = nn;
            nn->prev = tail;
 
            tail->next = nn;
        }
        else {
            nn->next = nn;
            nn->prev = nn;
            tail = nn;
        }
    }
 
    void clear()
    {
        cursor = tail;
    }
 
    int next()
    {
        if (cursor == 0) return -1;
        cursor = cursor->next;
        return cursor->value;
    }
 
    void del()
    {
        if (cursor == tail)
        {
            if (tail->prev == tail) tail = 0;
            else {
                tail = tail->prev;
            }
        }
 
        cursor->next->prev = cursor->prev;
        cursor->prev->next = cursor->next;
 
        cursor = cursor->prev == cursor ? 0 : cursor->prev;
    }
};
 
int main()
{
    int n, m;
    scanf("%d %d\n", &n, &m);
    LIST li;
    for (int i = n; i >= 1; i--)
    {
        li.insert(i);
    }
 
    li.clear();
    printf("<");
    for (int i = 1; i < n; i++)
    {
        int out;
        for (int j = 0; j < m; j++) {
            out = li.next();
        }
        printf("%d, ", out);
        li.del();
    }
 
    printf("%d>\n", li.next());
 
    return 0;
}

여담

시간 복잡도는 어떻게 될까요?

환형 큐를 m번 돌리는 것을 n번 반복하기 때문에 시간복잡도는 O(nm)이 됩니다!