[C++] 백준 5430번 AC [Gold5]

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

5430번: AC

풀이

덱을 사용해서 D이전에 R을 짝수 번 만났다면 pop_front(), 홀수 번 만났다면 pop_back() 해서 reverse 시키지 않고 원소를 제거할 수 있다. R의 총 개수를 세어서 짝수 번이라면 그대로 문자를 출력하고, 홀수 번이라면 뒤에서부터 출력한다.

1. 주어진 문자열에서 숫자만 골라내어 stoi() 함수를 사용해 덱에 저장한다.

2. 'R'일 경우 카운트하고, 'D'일 경우 현재까지 만난 'R' 수에 따라 앞/뒤에서 pop한다. 

3. 만약 덱의 크기가 0인데 pop할 경우 error를 출력하고 break 하여 커맨드 for loop을 빠져나간다(33% 틀렸습니다 요인).

4. break 되지 않았을 경우 r_cnt에 따라 앞/뒤 부터 출력하면 된다.

 

리뷰

덱의 장점을 잘 활용해야 했던 문제였다. 좋은 공부가 되었다.

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int T, n;
string p, arr;

deque<int> extractNum(string& a)
{
    deque<int> nums;
    string num="";
    for (int i=0; i<a.size(); i++) {
        if (a[i] != '[' && a[i] != ',' && a[i] != ']') {
            num += a[i];
        }
        else {
            if (num !="") {
                nums.push_back(stoi(num));
                num="";
            }
        }
    }    
    return nums;
}

void DF(deque<int>& a)
{
    a.pop_front();
}

void DB(deque<int>& a)
{
    a.pop_back();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    // freopen("5430.txt", "r", stdin);
    cin >> T; 
    for (int tc=0; tc<T; tc++) {
        cin >> p;
        cin >> n;
        cin >> arr;

        deque<int> vv;
        vv = extractNum(arr);
        int r_cnt=0;
        bool ch=false;
        for (int i=0; i<p.size(); i++) {
            if (p[i] == 'R') r_cnt++;
            if (p[i] == 'D') {
                if (r_cnt % 2 == 0) {
                    if (vv.size() != 0) DF(vv);
                    else { 
                        cout << "error" << "\n";
                        ch=true;
                        break;
                    }
                }
                else {
                    if (vv.size() != 0) DB(vv);
                    else { 
                        cout << "error" << "\n";
                        ch=true;
                        break;
                    }
                }
            }
        }
        if (ch) continue;
        if (vv.size() != 0) {
            // output
            cout << '[';
            if (r_cnt % 2 == 0) {
                for (int i=0; i<vv.size(); i++) {
                    if (i == vv.size()-1) cout << vv[i];
                    if (vv.size() > 1 && i != vv.size()-1) cout << vv[i] << ",";
                }
            }
            else {
                for (int i=vv.size()-1; i>=0; i--) {
                    if (i == 0) cout << vv[i];
                    if (vv.size() > 1 && i != 0) cout << vv[i] << ",";
                }
            }
            
            cout << ']' << "\n";
        }
        else {
            cout << "[]" << endl;
        }
        
    }
}