https://www.acmicpc.net/problem/20301
deque이란,
큐와 스택을 짬뽕시킨 자료구조다.
뒤로 들어온 데이터를 앞에서 꺼내거나 혹은 그 반대의 경우는 큐의 형태가 되고
뒤로 들어온 데이터를 뒤에서 꺼내거나 혹은 그 반대의 경우는 스택의 형태가 된다.#include<deque> : 전처리기 deque<Type> 변수명; 선언 변수명.push_back(데이터); : 덱의 뒤로 데이터 집어 넣기 변수명.push_front(데이터); : 덱의 앞으로 데이터 집어넣기 변수명.pop_back(); : 덱의 제일 마지막에 데이터 끄집어 내기 변수명.pop_front(); : 덱의 제일 앞에 데이터 끄집어 내기 변수명.begin() : 가장 앞의 원소 리턴 변수명.end() : 가장 뒤의 원소를 return empty() : 덱이 비어 있으면 true, 아니면 false 리턴 size() : 덱에 크기 리턴
- 앞에서부터 K-1번째까지는 가장 앞에 원소를 덱 가장 뒤에 해주고 push해주고 push해줬던 가장 앞에 원소는 바로 pop해준다.
- K번째 사람은 pop을 통해 제거한다.
- 만약 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++;
}
}