https://www.youtube.com/watch?v=0mEzJ4S1d8o
덱은 큐와 스택을 합친 느낌. front와 back만 확인할 수 있고, front와 back에 원소를 삽입, 삭제할 수 있다.
그래서 Vector와 비슷한 느낌이다.
https://www.acmicpc.net/problem/10866
10866번: 덱
첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지
www.acmicpc.net
덱 구현 문제였다.
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
deque<int> deq;
cin>>n;
while(n--){
string str;
cin>>str;
if(str=="push_front"){
int temp;
cin>>temp;
deq.push_front(temp);
}
else if(str=="push_back"){
int temp;
cin>>temp;
deq.push_back(temp);
}
else if(str=="pop_front"){
if(deq.empty()) cout<<-1<<'\n';
else{
cout<<deq.front()<<'\n';
deq.pop_front();
}
}
else if(str=="pop_back"){
if(deq.empty()) cout<<-1<<'\n';
else{
cout<<deq.back()<<'\n';
deq.pop_back();
}
}
else if(str=="size"){
cout<<deq.size()<<'\n';
}
else if(str=="empty"){
if(deq.empty()) cout<<1<<'\n';
else cout<<0<<'\n';
}
else if(str=="front"){
if(deq.empty()) cout<<-1<<'\n';
else cout<<deq.front()<<'\n';
}
else if(str=="back"){
if(deq.empty()) cout<<-1<<'\n';
else cout<<deq.back()<<'\n';
}
else return 0;
}
return 0;
}https://www.acmicpc.net/problem/1021
1021번: 회전하는 큐
첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가
www.acmicpc.net
오른쪽 이동을 해야 할 때와 왼쪽 이동을 해야 할 때를 어떻게 결정할 지 고민했던 문제였다. 생각해보니 굳이 구분하지 않고 한 쪽으로만 이동해도 풀 수 있었다.
1 2 3 4 5 6 7 8 9 10
여기서 2를 찾으려고 할 때.
<< 는 1번
>> 는 9번
둘의 합은 size이다.
이를 활용해 문제를 해결했다.
이 방식이면 덱이 아니라 큐로만으로도 해결할 수 있지 않을까? 라는 생각을 했는데 잘 모르겠다. 나중에 해보기로...
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int n,m,cnt=0;
deque<int> deq;
cin>>n>>m;
for(int i=1;i<=n;i++) deq.push_back(i);
for(int i=0;i<m;i++){
int num,count=0;
cin>>num;
while(deq.front()!=num){
int temp=deq.front();
deq.pop_front();
deq.push_back(temp);
count++;
}
int a=deq.size()-count;
int b=count;
cnt+=min(a,b);
deq.pop_front();
}
cout<<cnt;
return 0;
}https://www.acmicpc.net/problem/5430
5430번: AC
각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.
www.acmicpc.net
문제를 처음에 보면 어떻게든 될거같은 문제가 있는데 이게 그런 문제였다.
개인적으로 입력이 좀 까다로웠다. 입력 부분에서 어려움을 느껴서 정답 코드를 보았는데 cur을 사용해 해결했다. 이런 식으로 하면 n의 자릿수도 처리할 수 있다는 것을 알았다.
reverse 라는 함수를 알게 되었다.
또 출력을 할 때 pop도 같이 해야 하나 싶었는데 vector처럼 편하게 할 수 있었다.
골드 문제 중에서는 그래도 할 만 하지 않나 싶던 문제였다.
#include <bits/stdc++.h>
using namespace std;
void parse(string& str,deque<int>& d){
int cur=0;
for(int i=1;i<str.size()-1;i++){
if(str[i]==','){
d.push_back(cur);
cur=0;
}
else cur=10*cur + (str[i]-'0');
}
if(cur!=0) d.push_back(cur);
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
bool iswrong=false;
cin>>t;
while(t--){
string com,seq;
int n,size,rev=0;
deque<int> deq;
cin>>com>>n>>seq;
parse(seq,deq);
for(char c : com){
if(c=='R'){
rev=!rev;
}
if(c=='D'){
if(deq.empty()){ //에러
iswrong=true;
break;
}
else if(!rev) deq.pop_front();
else if(rev) deq.pop_back();
}
}
if(iswrong) cout<<"error\n";
else{
cout<<'[';
if(rev) reverse(deq.begin(),deq.end());
for(int i=0;i<deq.size();i++){
cout<<deq[i];
if(i!=deq.size()-1) cout<<',';
}
cout<<"]\n";
}
iswrong=false;
}
return 0;
}