백준 20301번: 반전 요세푸스, 덱

Se0ng_1l·2022년 7월 14일
0

백준

목록 보기
30/40

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

📌덱(deque)

deque이란,
큐와 스택을 짬뽕시킨 자료구조다.
뒤로 들어온 데이터를 앞에서 꺼내거나 혹은 그 반대의 경우는 큐의 형태가 되고
뒤로 들어온 데이터를 뒤에서 꺼내거나 혹은 그 반대의 경우는 스택의 형태가 된다.

#include<deque> : 전처리기
deque<Type> 변수명; 선언
변수명.push_back(데이터); : 덱의 뒤로 데이터 집어 넣기
변수명.push_front(데이터); : 덱의 앞으로 데이터 집어넣기
변수명.pop_back(); : 덱의 제일 마지막에 데이터 끄집어 내기
변수명.pop_front(); : 덱의 제일 앞에 데이터 끄집어 내기
변수명.begin() : 가장 앞의 원소 리턴
변수명.end() : 가장 뒤의 원소를 return
empty() : 덱이 비어 있으면 true, 아니면 false 리턴
size() : 덱에 크기 리턴

📌문제 접근

  1. 앞에서부터 K-1번째까지는 가장 앞에 원소를 덱 가장 뒤에 해주고 push해주고 push해줬던 가장 앞에 원소는 바로 pop해준다.
  2. K번째 사람은 pop을 통해 제거한다.
  3. 만약 m번 사람을 제거했다면 1번과정의 앞과 뒤를 반대로 해준다.
    가장 마지막 원소를 앞에 push하고 가장 뒤에 원소를 pop.
#include <iostream>
#include <deque>
using namespace std;

int main()
{
    deque<int> deq;
    int n, k, m;
    cin >> n >> k >> m;
    for(int i = 1; i <= n; i++)
        deq.push_back(i);
    int cnt = 1;
    bool chk = false;
    while(!deq.empty())
    {
        for(int i = 0; i < k - 1; i++)
        {
            if(!chk)
            {
                deq.push_back(deq.front());
                deq.pop_front();
            }
            else
            {
                deq.push_front(deq.back());
                deq.pop_back();
            }
        }
        if(!chk)
        {
            cout << deq.front() << endl;
            deq.pop_front();
        }
        else
        {
            cout << deq.back() << endl;
            deq.pop_back();
        }
        if(cnt % m == 0){
            chk = !chk;
        }
        cnt++;
    }
}
profile
치타가 되고 싶은 취준생

0개의 댓글