[c++]백준 2164번: 카드2 (원형 큐 구현 & 군수열)

문제

https://www.acmicpc.net/problem/2164

 

풀이

 

🚩원형 큐

앞에 카드를 빼고 뒤로 넣는다? -> 선입선출 -> queue 문제구나.

 

라이브러리를 사용하면 쉽게 풀 수 있고, 클래스로 직접 구현해서 풀어도 된다. 

나는 겸사겸사 queue 라이브러리를 꼼꼼히 볼겸 간단하게 직접 구현해서 풀었다. 

 

Queue 라이브러리의 내부 코드가 궁금하면 아래 사이트를 참조하면 된다.

https://en.cppreference.com/w/cpp/container/queue

 

🚩군수열

서치 하다가 군수열로 규칙찾는 방법도 있더라..  근데 난 못 알아들음 (〃⌒▽⌒〃)ゝ  

https://hoho325.tistory.com/138

 

소스

#include <iostream>
#define MAX_SIZE 500001

class Queue {
    
public:
    int count;
    
    Queue(int n): size(n), front(-1), rear(-1), count(0){};
    
    bool isFull()
    {
        if ((front == 0 && rear == size - 1) || (front == rear + 1))
            return true;
        else
            return false;
    }
    
    bool isEmpty()
    {
        if (front == -1)
            return true;
        else
            return false;
    }
    
    void enQueue(int data)
    {
        if (!isFull())
        {
            if (front == -1) front = 0;
            rear = (rear + 1) % size;
            items[rear] = data;
            ++count;
        }
    }
    
    int deQueue()
    {
        if (isEmpty())
            return (-1);
        
        int data = items[front];
        if (front == rear)
        {
            front = -1;
            rear = -1;
        }
        else
        {
            front = (front + 1) % size;
        }
        --count;
        return data;
    }
    
    void display()
    {
        std::cout << "\ndisplay---------------\n";

        for(int i = 0; i<size; ++i)
        {
            std::cout << items[i] << "\t";
        }
        std::cout << "\n----------------------\n";
    }
    
private:
    int items[MAX_SIZE];
    int front, rear;
    int size;
    
    
};

int main()
{
    int N = 0;
    std::cin >> N;
    if(N==1)
    {
        std::cout << N << std::endl;
        return 0;
    }
    
    Queue q(N);
    q.deQueue();
    for(int i = 1; i<=N; ++i)
    {
        q.enQueue(i);
    }
    while(1)
    {
        if(q.count == 1)
        {
            std::cout << q.deQueue() << std::endl;
            break;
        }
        q.deQueue();
        q.enQueue(q.deQueue());

    }
    
    return 0;
}