[백준(BOJ)] 5430번 : AC - C++[CPP]

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

5430번: AC

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 구현
• 자료 구조
• 문자열
• 파싱
• 덱

 

---

 

⊙ 문제 접근 과정

 

deque으로 문제를 풀었다. 그리고 boolean을 적극 활용했다.

앞 뒤 값을 사용한다고하면 deque가 자동으로 생각나야한다.

 

기억하자 queue는 단방향, deque는 양방향

 

첫 시도 코드는 시간 초과가 떴다.

명령어에 R이 나올 때마다 reverse()를 사용하면 제한 시간인 1초 안에 절대 풀지 못한다.

명령어의 수가 최대 100,000인데 극단적으로 R이 100,000번 입력되었다고 생각해보자.

R 명령어를 수행할 때마다 reverse() 함수를 사용하면 시간 초과를 피할 수 없다.

 

그래서 떠올린게 boolean을 이용하였다.

 

R이 들어오면 boolean 값을 변경해주고 bool 값이 true면 pop_back() 함수를,

false면 pop_front() 함수를 사용해줬다.

 

애러 부분도 bool flag를 사용하여 애러 조건마다 flag를 true 값으로 변경해줬다.

최종 출력때 해당 케이스의 flag 값이 false면 배열 출력, true면 error를 출력하도록 했다.

 

---

 

⊙ 문제 풀이

 

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

using namespace std;

int T,N;
int inx=0;
bool flag=false;
bool rev=false;
string p;
string arr;
string temp;
deque<string> dq;


void order() {
    if(N==0) {
        if(p[0]=='D') {
            flag=true;
        }
    }
    for(int i=0;i<p.length();i++) {
        if(flag) break;
        if(p[i]=='R') {
            if(rev) {
                rev=false;
            } else rev=true;
        }else if(p[i]=='D') {
            if(dq.size()==0) {
                flag=true;
                break;
            }
            if(rev)
                dq.pop_back();
            else dq.pop_front();
        }else {
            flag=true;
        }
    }
}

void dq_plus() {
    for(int i=1;i<=arr.length();i++) {
        if((arr[i]!=',') && (arr[i]!=']')) {
            inx++;
        } else {
            for(int j=inx;j>0;j--) {
                temp+=arr[i-j];
                }
            dq.push_back(temp);
            inx=0;
            temp="";
        }
    }
    if(dq.size()!=0) {
        order();
    } else flag=true;
}

void reset() {
    inx=0;
    flag=false;
    rev=false;
    p="";
    arr="";
    temp="";
    dq.clear();
}

int main() {
    ios::sync_with_stdio(false);
	cin.tie(0);
    cin >> T;

    while(T--) {
        reset();
        cin >> p;
        cin >> N;
        cin >> arr;
        dq_plus();
        
        if(!flag) {
            cout << "[";
            if(rev) reverse(dq.begin(),dq.end());
            for(int i=0;i<dq.size();i++) {
                cout << dq[i];
                if(i!=dq.size()-1)
                    cout << ",";
            }
            cout << "]\n";
        } else {
            cout << "error\n";
        }
    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

좋아요는 로그인하지 않아도 누를 수 있습니다!