시작과 끝 모두에서 입력과 출력이 가능함
덱의 성질
1.원소의 추가 제거가 O(1)
2.제일 앞/뒤의 원소의 확인이 O(1)
3.시작과 끝을 제외한 원소를 확인할수없음
10866 . 덱
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
deque <int> d;
for (int i = 0; i < n; i++)
{
string command;
cin >> command;
int input = 0;
if (command == "push_front")
{
cin >> input;
d.push_front(input);
}
else if (command == "push_back")
{
cin >> input;
d.push_back(input);
}
else if (command == "pop_front")
{
if (d.empty())
{
cout << "-1\n";
}
else
{
cout << d.front() << "\n";
d.pop_front();
}
}
else if (command == "pop_back")
{
if (d.empty())
{
cout << "-1\n";
}
else
{
cout << d.back() << "\n";
d.pop_back();
}
}
else if (command == "size")
{
cout << d.size() << "\n";
}
else if (command == "empty")
{
cout << d.empty() << "\n";
}
else if (command == "front")
{
if (d.empty())
{
cout << "-1\n";
}
else
{
cout << d.front() << "\n";
}
}
else if (command == "back")
{
if (d.empty())
{
cout << "-1\n";
}
else
{
cout << d.back() << "\n";
}
}
}
}STL 덱의 명령어들을 적재적소에 사용하면 해결할수있다.
1021.회전하는 큐
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,ans = 0;
cin >> n;
deque <int> d;
for (int i = 1; i <= n; i++)
{
d.push_back(i);
}
int cnt;
cin >> cnt;
for (int i = 0; i < cnt; i++)
{
int find = 0;
cin >> find;
int index = 0;
for (int i = 0; i < d.size(); i++)
{
if (d[i] == find)
{
index = i;
break;
}
}
if (index <= (d.size())- index)
{
while (1)
{
if (d.front() == find)
{
d.pop_front();
break;
}
d.push_back(d.front());
d.pop_front();
ans++;
}
}
else
{
while (1)
{
if (d.front() == find)
{
d.pop_front();
break;
}
d.push_front(d.back());
d.pop_back();
ans++;
}
}
}
cout << ans << '\n';
}우선 1부터 N 까지의 정수를 덱에 넣어준다 (뽑으려는 위치값이 숫자가 빠진다고해서 달라지는것이아닌 초기의 위치값을 의미하므로) 다음 이 위치값이 왼쪽으로 돌렸을때 빨리 빠지는지 오른쪽으로 돌렸을때 빨리 빠지는지를 찾아내야 한다. 이 때 단순히 덱의 사이즈의 반보다 값이 작은지 큰지를 비교해서는 알수없다 숫자를 빼기위해 계속 위치값이 변하기 때문이다. 때문에 for문 을통해 현재 find값의 인덱스를 찾고 이 인덱스가 d.size()의 중앙값보다 왼쪽에있는지 오른쪽에있는지를 찾는다.
만약 왼쪽에있다면 왼쪽으로 회전하면 ans값을 증가시키고 오른쪽에있다면 오른쪽으로 회전시켜준다 여기서 오른쪽으로 회전할경우에도 값을 확인하는것은 back이아니라 front임을 명심해야한다.
- AC
#include <bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
string command;
cin >> command;
int len;
cin >> len;
deque <int> d;
string arr;
cin >> arr;
int num = 0;
for (char c : arr)
{
if (c == '[')
continue;
else if (c == ',' || c == ']')
{
if (num != 0)
{
d.push_back(num);
num = 0;
}
}
else
{
num *= 10;
num += c - '0';
}
}
bool bErr = 0;
bool bRev = 0;
for (char c : command)
{
if (c == 'R')
{
bRev = !bRev;
}
else
{
if (d.empty())
{
bErr = true;
break;
}
else
{
if (bRev)
{
d.pop_back();
}
else
{
d.pop_front();
}
}
}
}
if (bErr)
{
cout << "error\n";
}
else
{
if (bRev)
{
cout << '[';
while (!d.empty())
{
cout << d.back();
d.pop_back();
if (!d.empty())
{
cout << ',';
}
}
cout << "]\n";
}
else
{
cout << '[';
while (!d.empty())
{
cout << d.front();
d.pop_front();
if (!d.empty())
{
cout << ',';
}
}
cout << "]\n";
}
}
}
}만약 직관적으로 덱을 R 명령어가 들어올때마다 뒤집는다면 뒤집는연산이 O(N)의 시간이 들기때문에 시간초과를 맞는다 이를 해결하기위해선 bool변수 하나로 해결이 가능하다 R이 들어올때마다 bRev를 전환하며 뒤집힌경우엔 pop과 출력을 반대로 해주는것이다. 또한 덱이 비어있는 상태에서 D명령어가 들어오면 에러를 출력해주는 예외처리를 해주어야한다.
다음으로 체크해주어야할 부분은 배열이 [1,2,3] 형식으로 들어오기때문에 문자열 처리를 해주어여한다 단순히 숫자를 입력받으면 2,3자리 숫자를 받을수없기때문에 숫자가 들어오는동안 10을 곱해주며 저장해주어야하고 아무 숫자도 들어오지않을 경우 0을 저장하지않게 num이 0인경우는 덱에 넣지않게 처리해주어야한다.
