[BOJ] 2161번 문제 카드1, 2164번 문제 카드2

카드1 문제 링크

카드2 문제 링크

어떻게 풀까?

두 문제는 N만 다르지 거의 같은 문제입니다!

두 문제를 풀기 위해 리스트를 사용했습니다.

카드 1의 경우에는 리스트에서 맨 앞에 하나는 출력하고 리스트에서 삭제합니다.

그리고 또다시 맨 앞의 수를 삭제하고 맨 뒤에 넣습니다.

이 행동을 n-1번 반복하면 마지막 카드가 남고, 이 카드를 출력해주면 됩니다!

예제를 한번 풀어보겠습니다!

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

맨 앞에있는 수는 출력하고, 2는 삭제한 뒤에 맨 뒤에 다시 넣어줍니다.

이제 맨 앞의 수가 3이 되고, 해당 수를 출력하고 삭제합니다.

4는 삭제하고 맨 뒤로 보냅니다.

이제 맨 앞의 수는 7이 됩니다. 7을 출력하고 리스트에서 삭제합니다.

2도 리스트에서 삭제 후에 맨 뒤에 다시 넣어줍니다.

이제 4번이 리스트의 맨 앞에 오게 됩니다. 

6은 리스트에서 삭제후 다시 맨 뒤에 넣어줍니다.

이제 2를 출력하고 삭제합니다.

마지막으로 6을 출력하면 완성됩니다!

카드 2번의 경우는 더 간단합니다.

카드 1에서 했던 행동에서 맨 앞에 하나를 출력하고 리스트를 삭제하는 부분에서 출력만 안하면 됩니다.

즉, 카드 2의 경우에는 리스트에서 맨 앞에 하나는 리스트에서 삭제하고, 맨 뒤의 리스트는 삭제한 뒤에 다시 맨 뒤에 넣어주면 됩니다.

코드(카드 1)

#pragma once
#include<cstdio>
 
struct NODE
{
    int value;
    NODE* prev;
    NODE* next;
    
    NODE()
    {
        prev = next = 0;
    }
};
 
static struct MYMAL
{
    NODE nodes[10000];
    int idx;
    MYMAL()
    {
        idx = 0;
    }
    void clear()
    {
        idx = 0;
    }
    NODE* malloc()
    {
        return &nodes[idx++];
    }
 
 
} MYMAL;
 
struct LIST
{
    NODE *head, *tail;
    NODE *cursor[2];
 
    LIST()
    {
        head = MYMAL.malloc();
        tail = MYMAL.malloc();
        head->next = tail;
        tail->prev = head;
    }
    
    void insert_front(int i)
    {
        NODE *nn = MYMAL.malloc();
        nn->value = i;
        nn->next = head->next;
        nn->prev = head;
 
        head->next->prev = nn;
        head->next = nn;
    }
 
    void insert_back(int i)
    {
        NODE* nn = MYMAL.malloc();
        nn->value = i;
        nn->next = tail;
        nn->prev = tail->prev;
 
        tail->prev->next = nn;
        tail->prev = nn;
    }
 
    void clear_front()
    {
        cursor[0] = head;
    }
    void clear_back()
    {
        cursor[1] = tail;
    }
 
    int next()
    {
        if(cursor[0]->next != tail) cursor[0] = cursor[0]->next;
 
        return cursor[0]->value;
    }
 
    int prev()
    {
        if (cursor[1]->prev != head) cursor[1] = cursor[1]->prev;
        return cursor[1]->value;
    }
 
    void del_front()
    {
        if (cursor[0] != head)
        {
            cursor[0]->prev->next = cursor[0]->next;
            cursor[0]->next->prev = cursor[0]->prev;
            cursor[0] = cursor[0]->prev;
        }
    }
 
    void del_back()
    {
        if (cursor[1] != tail)
        {
            cursor[1]->prev->next = cursor[1]->next;
            cursor[1]->next->prev = cursor[1]->prev;
            cursor[1] = cursor[1]->next;
        }
    }
};
 
int main()
{
    int n;
    scanf("%d\n", &n);
    LIST li;
    
    for (int i = 1; i <= n; i++)
    {
        li.insert_back(i);
    }
 
    li.clear_back();
    li.clear_front();
 
    for (int i = 1; i < n; i++) {
        int out = li.next();
        printf("%d ", out);
        li.del_front();
 
        out = li.next();
        li.del_front();
        li.insert_back(out);
    }
    printf("%d\n", li.next());
 
    return 0;
}

코드(카드 2)

#pragma once
#include<cstdio>
 
struct NODE
{
    int value;
    NODE* prev;
    NODE* next;
    
    NODE()
    {
        prev = next = 0;
    }
};
 
//malloc을 쓰기 싫었음.
static struct MYMAL
{
    NODE nodes[2000000];
    int idx;
    MYMAL()
    {
        idx = 0;
    }
    void clear()
    {
        idx = 0;
    }
    NODE* malloc()
    {
        return &nodes[idx++];
    }
 
 
} MYMAL;
 
struct LIST
{
    NODE *head, *tail;
    NODE *cursor[2];
 
    LIST()
    {
        head = MYMAL.malloc();
        tail = MYMAL.malloc();
        head->next = tail;
        tail->prev = head;
    }
    
    void insert_front(int i)
    {
        NODE *nn = MYMAL.malloc();
        nn->value = i;
        nn->next = head->next;
        nn->prev = head;
 
        head->next->prev = nn;
        head->next = nn;
    }
 
    void insert_back(int i)
    {
        NODE* nn = MYMAL.malloc();
        nn->value = i;
        nn->next = tail;
        nn->prev = tail->prev;
 
        tail->prev->next = nn;
        tail->prev = nn;
    }
 
    void clear_front()
    {
        cursor[0] = head;
    }
    void clear_back()
    {
        cursor[1] = tail;
    }
 
    int next()
    {
        if(cursor[0]->next != tail) cursor[0] = cursor[0]->next;
 
        return cursor[0]->value;
    }
 
    int prev()
    {
        if (cursor[1]->prev != head) cursor[1] = cursor[1]->prev;
        return cursor[1]->value;
    }
 
    void del_front()
    {
        if (cursor[0] != head)
        {
            cursor[0]->prev->next = cursor[0]->next;
            cursor[0]->next->prev = cursor[0]->prev;
            cursor[0] = cursor[0]->prev;
        }
    }
 
    void del_back()
    {
        if (cursor[1] != tail)
        {
            cursor[1]->prev->next = cursor[1]->next;
            cursor[1]->next->prev = cursor[1]->prev;
            cursor[1] = cursor[1]->next;
        }
    }
};
 
int main()
{
    int n;
    scanf("%d\n", &n);
    LIST li;
    
    for (int i = 1; i <= n; i++)
    {
        li.insert_back(i);
    }
 
    li.clear_back();
    li.clear_front();
 
    for (int i = 1; i < n; i++) {
        int out = li.next();
        li.del_front();
 
        out = li.next();
        li.del_front();
        li.insert_back(out);
    }
    printf("%d\n", li.next());
 
    return 0;
}

여담

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

리스트에 넣고 빼는 일을 n번 반복하므로, 두 문제 모두 시간복잡도는 O(n)입니다.