[백준 5430] AC

AC

문제 설명

AC라는 언어에 R, D 두가지 함수가 존재한다. R은 뒤집기, D는 첫 번째 숫자를 지운다.
이때 입력으로는 테스트 케이스 수 (T)가 주어지고, 숫자의 수, 배열 [x1,x2,...]이 주어진다.
각각 함수 실행 결과를 출력 시킨다.
이때 배열에 숫자가 없는데 D를 실행시키면 error를 출력시킨다.

---

알고리즘

1. 필요한 입력들을 받고, 배열을 deque에 넣어준다. 이때 배열에 넣을 때 숫자의 범위는 1부터 100까지인 것을 감안하고 처리하여 넣는다.
2. R과 D를 차례차례 읽어서 실행한다.
3. R의 경우 반복문 내에서 실행하면 시간초과가 발생하므로 bool type flag를 not을 사용하여 처리한다.
4. D의 경우 deque의 비어있는지 여부를 확인하고 비어있는 경우 error를 출력한다. 비어있지 않으면 flag의 여부에 따라 뒤집기(flag==true)인 경우 deque의 뒤에서 제거하고, 그렇지 않은 경우 (flag==false) 앞에서 제거한다.
5. 함수 read가 끝나면 결과를 출력한다.
6. 테스트 케이스 만큼 실행이 완료되면 종료시킨다.

#include <stdio.h>
#include <iostream>
#include <deque>
#include <string>
#include <algorithm>
using namespace std;

int main()
{    
    int T;
    cin >> T;
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cout.tie(NULL);
    for (int i = 0; i < T;i++)
    {
        string function;
        int num;
        string arr;
        deque <int> q;//덱 선언 
        bool check = true;//error를 처리해 주기 위한 flag
        bool flag = false;//R을 처리해 주기 위한 flag
        int cnt = 0;
        cin >> function >> num >> arr;// 필요 한 입력 받기

        string p;
        for (int j = 0; j < arr.length(); j++)//입력 받은 숫자를 deque 에 넣는 행위 
        {    
            if (num == 0)
                break;
            if (arr[j] >= '0' && arr[j] <= '9')
                p += arr[j];
            else if (arr[j] == ','|| j==arr.length()-1)
            {
                q.push_back(stoi(p));
                p.clear();
            }
        }

        for (int i = 0; i < function.length(); i++)//함수를 실행하기 위한 반복문 
        {
            if (function[i] == 'R')//뒤집기 함수 
            {
                flag = !flag;
            }
            else if (function[i] == 'D')//원소 하나 지우기 함수
            {
                if (q.empty())//queue가 비었는데 빼는 경우
                {
                    cout << "error" << "\n";
                    check = false;
                    break;
                }
                else //R이 실행 된 경우 뒤에서 빼고 그렇지 않은 경우는 앞에서 제거
                {
                    if (flag)
                        q.pop_back();
                    else
                        q.pop_front();
                }
            }
        }
        if (flag)//뒤집기가 필요한 경우 
            reverse(q.begin(), q.end());
        if(check==true)
        cout << "[" ;
        while (!q.empty())//덱에 들어있는 값 출력
        {
            cout << q.front();
            q.pop_front();
            if (q.size() >=1)
                cout << ",";
        }    if (check == true) cout <<"]"<< "\n";
    }

    return 0;
}

---

고찰

단순하게 queue로 구현할 수 있을 것이라고 생각해서 구현했더니 뒤집기(R)에서 시간초과가 발생한다.
따라서 앞에서만 접근 가능한 queue와는 다르게 앞이나 뒤로 모두 접근이 가능한 deque의 사용이 필요하다.

막혔던 부분

• 배열을 deque에 넣는 과정 -> 처음에 1글자 일때로 짜서 3글자일 때 까지를 고려하지 못했다.
• 뒤집기 시간 초과 -> deque를 사용하고 R이 들어왔을 때 바로 뒤집지 않고 flag라는 bool type변수를 사용하여 함수의 연산이 끝난 뒤 처리한다.

---

새로 배운 개념

1. cin, cout 의 시간을 줄이기 위한 코드 -> 버퍼를 지워서 시간을 단축+) cout<<endl 이라고 출력하는 부분도 시간을 지연시키니 cout<<"\n"으로 바꿔서 출력시키자
2. cin.tie(NULL); ios::sync_with_stdio(false); cout.tie(NULL);
3. deque<deque 사용 가능 함수>
   • dq.pop_front(): deque에서 앞부분 값 삭제
   • dq.pop_back(): deque에서 뒷부분 값 삭제
   • dq.push_back(): deque에서 뒷부분에 값 삽입
   • dq.push_front(): deque에서 앞부분에 값 삽입
4. 1) 헤더 파일 #include
   2) 연산자들 모두 사용 가능
   3) vector의 단점을 보안하고자 만들어진 container
   4) queue와 다르게 앞과 뒤 모두 접근 가능