[알고리즘] 백준 5430 AC // 덱, 구현

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

 

 

* 풀이1

#include <bits/stdc++.h>
using namespace std;   

int t;

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cin >>t;

   while(t--) {
      string s1,s2;
      int n;
      cin>>s1>>n>>s2;
      deque<int> d;

      
      if(s2!="[]") {
         s2 = s2.substr(1,s2.size()-2); // [, ] 날리기
         string buf="";
         for(auto c : s2) {
            if(c==',') {
               d.push_back(stoi(buf));
               buf="";
            }
            else {
               buf+=c;
            }
         }
         if(buf!="") d.push_back(stoi(buf));
      }
      
      // for(auto i : d) {
      //    cout<<i<<" ";
      // }

      // 명령어 수행
      int flag = 1; // 1:앞, 0:뒤
      int err=0;
      for(auto c : s1) {
         if(c=='R') {
            flag^=1;
         }
         if(c=='D') {
            if(d.empty()) {
               err=1;
               break;
            }
            if(flag) {
               d.pop_front();
            }
            if(!flag) {
               d.pop_back();
            }
         }
      }
      if(err) {
         cout<<"error\n";
         continue;
      }
      string ans="[";
      if(!flag) reverse(d.begin(),d.end());
      for(auto i : d) {
         ans+=to_string(i);
         ans+=",";
      }
      ans=ans.substr(0,ans.size()-1);
      ans+="]\n";
      cout<<ans;
   }

   
  
   return 0;
}

• 문제점 1
  • string을 찍지말고 처음과끝은 cout [ ] 해주도록 개선

• 문제점2
  • flag에따라 덱을 뒤에서부터 탐색
  • reverse함수로 1줄로 개선

 

 

* 풀이2

#include <bits/stdc++.h>
using namespace std;   

int t;

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0);
   cin >>t;

   while(t--) {
      string s1,s2;
      int n;
      cin>>s1>>n>>s2;
      deque<int> d;

      
      if(s2!="[]") {
         s2 = s2.substr(1,s2.size()-1); // [ ...  ] 날리기
         string buf="";
         for(auto c : s2) {
            if(c==',') {
               d.push_back(stoi(buf));
               buf="";
            }
            else {
               buf+=c;
            }
         }
         if(buf!="") d.push_back(stoi(buf));
      }
      
      // for(auto i : d) {
      //    cout<<i<<" ";
      // }

      // 명령어 수행
      int flag = 1; // 1:앞, 0:뒤
      int err=0;
      for(auto c : s1) {
         if(c=='R') {
            flag^=1;
         }
         if(c=='D') {
            if(d.empty()) {
               err=1;
               break;
            }
            if(flag) {
               d.pop_front();
            }
            if(!flag) {
               d.pop_back();
            }
         }
      }
      if(err) {
         cout<<"error\n";
         continue;
      }
      cout << "[";
      if(!d.empty()) {  // deque가 비어있지 않을 때만 처리
         if(!flag) reverse(d.begin(),d.end());
         for(int i = 0; i < d.size()-1; i++) {
            cout << d[i] << ",";
         }
         cout << d.back();  // 마지막 원소는 쉼표 없이 출력
      }
      cout << "]\n";
   }

   
  
   return 0;
}

• 문제점
  • substr을 호출할필요 x
  • [, ] 인경우,  컨틴뉴하면됨

• 문제점2
  • stoi 는 오버플로우 위험
  • *10 + 로 개선

 

* 풀이3 (큰돌)

#include <bits/stdc++.h>
using namespace std;
int T, N, x;
string P, order;
int main(){ 
	cin >> T;  
    for(int t = 0; t < T; t++){ 
        deque<int> D;
        cin >> P >> N >> order;
        x = 0;
        for(char c : order){
        	if(c == '[' || c == ']') continue;
        	// 숫자가 나오면 현재 수*10 한 뒤 더함
            if(c >= '0' && c <= '9') x = x*10 + c-'0';
            // 아닐 경우 현재 수를 덱에 넣음
            else{
                if(x > 0) D.push_back(x);
                x = 0; 
            }
		} 
		if(x > 0) D.push_back(x);
        // 초기에는 에러 없음, 뒤집히지 않은 상태
        bool error = false, rev = false;
 		for(char a : P){
 			if(a == 'R') rev = !rev; 
 			else{
                // 비어있는데 제거하려 하면 에러
                if(D.empty()){
                    error = true;
                    break;
                }
                if(rev) D.pop_back();
                else D.pop_front(); 
			}
		}  
        // 에러가 발생한 경우
        if(error) cout << "error" << '\n';
        // 아닐 경우 덱의 원소를 하나하나 출력
        else{
        	cout << "["; 
            // 덱이 뒤집힌 상태면 진짜로 뒤집어 준다.
            if(rev) reverse(D.begin(), D.end());
            for(int i = 0; i < D.size(); i++){
        		cout << D[i];  
                if(i < D.size()-1) cout << ",";
            }
        	cout << "]\n";  
        }
    }
}