[BOJ 5430번/C++] AC

미숙한 블로그 주인이 코딩테스트 문제를 풀어가는 과정을 담은 글입니다. 이 풀이가 효율적인 풀이가 아닐 수 있으며, 부정확한 정보가 많이 있을 수 있습니다. 보완해야할 점이 있다면 댓글로 남겨주세요!

 

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

5430번: AC

AC

문제

문제

선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다.

함수 R은 배열에 있는 수의 순서를 뒤집는 함수이고, D는 첫 번째 수를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다.

함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. 예를 들어, "RDD"는 배열을 뒤집은 다음 처음 두 수를 버리는 함수이다.

배열의 초기값과 수행할 함수가 주어졌을 때, 최종 결과를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. T는 최대 100이다.

각 테스트 케이스의 첫째 줄에는 수행할 함수 p가 주어진다. p의 길이는 1보다 크거나 같고, 100,000보다 작거나 같다.

다음 줄에는 배열에 들어있는 수의 개수 n이 주어진다. (0 ≤ n ≤ 100,000)

다음 줄에는 [x1,...,xn]과 같은 형태로 배열에 들어있는 정수가 주어진다. (1 ≤ xi ≤ 100)

전체 테스트 케이스에 주어지는 p의 길이의 합과 n의 합은 70만을 넘지 않는다.

출력

각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다.

 

풀이

문제에서 R을 할 때마다 뒤집으래서 정말로 배열을 뒤집으면 안 된다.

뒤집는 연산은 최대 100,000번이고 원소의 최대 수가 100,000번이기에 최악의 경우 100억번 연산을 해야한다.

즉, 시간 초과가 발생할 가능성이 매우 높다.

 

그러면 뒤집는 연산은 어떻게 처리할까?

다르게 생각하면 뒤집는 연산은 앞에서 시작했다면 뒤에서 시작하게, 뒤에서 시작했다면 앞에서 시작하게 바꾸는 연산이다.

 

즉, 앞에서 삭제가 일어나고 있다가 뒤집는 연산을 만나면 뒤에서 삭제가 일어나도록 하면 되는 것이다.

 

이제 이걸 어떻게 구현할까하니 우리에게는 Deque라는 비장의 무기(?)가 있다.

Deque는 앞에서도 삽입과 삭제가, 뒤에서도 삽입과 삭제가 일어나는 자료구조이다.

그러니, R을 만날 때 마다 pop_front와 pop_back을 바꿔가며 사용해주면 되는 문제였다!

 

#include <iostream>
#include <deque>
#include <string>

#define endl '\n'

using namespace std;

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);

    int T;
    cin >> T;

    string p;
    int n;
    string arr;
    deque<int> dq;
    bool is_forward = true;
    bool is_error = false;
    for (int t = 0; t < T; t++) {
        cin >> p >> n >> arr;

        string tmp = "";
        if (n > 0) {
            for (int i = 1; i < arr.length() - 1; i++) {
                if (arr[i] == ',') {
                    dq.push_back(stoi(tmp));
                    tmp = "";
                }
                else {
                    tmp += arr[i];
                }
            }
            dq.push_back(stoi(tmp));
        }

        is_forward = true;
        is_error = false;
        for (int i = 0; i < p.length(); i++) {
            if (p[i] == 'R') {
                is_forward = !is_forward;
            }
            else {
                if (n == 0) {
                    is_error = true;
                    break;
                }
                else {
                    if (is_forward) {
                        dq.pop_front();
                        n--;
                    }
                    else {
                        dq.pop_back();
                        n--;
                    }
                }
            }
        }

        string print_buff = "";
        if (!is_error) {
            print_buff += "[";
            while (!dq.empty()) {
                if (is_forward) {
                    print_buff += to_string(dq.front());
                    dq.pop_front();
                }
                else {
                    print_buff += to_string(dq.back());
                    dq.pop_back();
                }
                print_buff += ",";
            }

            if (print_buff[print_buff.length() - 1] == ',')
                print_buff[print_buff.length() - 1] = ']';
            else
                print_buff += "]";
        }
        else {
            print_buff = "error";
        }
        cout << print_buff << endl;
    }

    return 0;
}