[ 백준 ] 5430 / AC

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
131/228
post-thumbnail

# Appreciation

/*
 * Problem :: 5430 / AC
 *
 * Kind :: Data Structure
 *
 * Insight
 * - 연산이 단 두가지다
 *   + 뒤집는다
 *   + 맨 앞을 버린다
 *   # 그냥 R 나올 때마다 Vector 뒤집으면 되지 않을까?
 *     -> max(T) = 10^2, max(len(p)+len(n)) = 7*10^5
 *        max(All) = 7*10^7
 *        제한시간 1초면 10^8 까지 괜찮은 거니...
 *        O(n) 으로 풀어야 한다! <= 뒤집는 연산따위는 사용할 수 없다
 *        역시 그렇게 쉬운 방법으로 풀려질리가 없다
 *
 * - 배열의 상태는
 *   뒤집어진 상태와 그렇지 않은 상태, 두 가지로나눌 수 있다
 *   그렇다면 연산도 이에 맞춰서
 *   뒤집어진 상태에서 앞의 원소를 버리는 경우와
 *   그렇지 않은 상태에서 앞의 원소를 버리는 경우로 생각할 수 있다
 *   + Deque 이네...?
 *     # Deque 이다
 *       -> pop_front, pop_back
 *
 * Point
 * - 입력으로 주어지는 정수 배열이
 *   공백으로 구분되어 있지 않다 <= cin 못 쓴다
 *   + C++ 에 Java 나 Python 의 split 과 같은 함수 있나 찾아보다가
 *     <sstream>, getline(stringstream, buffer, delimiter)
 *     과 같은 좋은 STL 이  있다는 것을 알게 되었다 <= 좋은 건 써야지
 *     # 물론 배열의 앞에서 하나씩 숫자인지, 콤마인지, 대괄호인지에 따라 다르게 처리하며
 *       주어진 정수를 구할 수도 있다 <= 위에꺼보다 귀찮을 뿐
 *
 * - 출력도 괄호를 쳐주어야 하는데
 *   배열이 빈 경우와 그렇지 않은 경우를 잘 구분해서 출력해주자 <= Off-by-one error
 *   + [] -> 빈 배열
 *   + [23] -> 원소가 한 개인 배열
 *   + [23,12,99] -> 원소가 둘 이상인 배열
 *
 * - 문제이름의 상태가...?
 *   + AC (에이씨...?)
 *   + ㅁㅊ (한글도...?)
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

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

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int T; cin >> T;

    while (T--) {
        string P; cin >> P;
        int N; cin >> N;
        string X; cin >> X;

        // Process
        X = X.substr(1, X.length()-2); /* 대괄호 제거 */
        stringstream ss(X);
        string buffer;
        deque<string> nums;
        while (getline(ss, buffer, ',')) { /* ',' 을 구분자로 하여 문자열 파싱 */
            nums.push_back(buffer);
        } bool isReversed = false; /* 현재 배열이 뒤집어진 상태인지 확인 */

        bool isError = false; /* 명령 실행중 에러가 발생했는지 확인 */
        for (char cmd : P) {
            if (isError) break; /* 에러가 발생했다면 이후 명령어를 실행할 필요 없음 */
            switch (cmd) {
                case 'R':
                    /* 배열을 실제로 뒤집는 것이 아님, 배열의 상태만 갱신해줌
                     * 이렇게만 해도 이후에 주어지는 모든 연산을
                     * 상태에 따라 적절히 처리할 수 있음 */
                    isReversed ^= true;
                    break;

                case 'D':
                    if (nums.empty()) { /* 배열이 비었는데 원소를 버리려 하면 */
                        isError = true; /* 에러 발생 */
                        break;
                    } else {
                        /* 배열이 뒤집어진 상태라면 가장 뒷 원소를 제거,
                         * 그렇지 않다면 가장 앞 원소를 제거 */
                        (isReversed) ? nums.pop_back() : nums.pop_front();
                    } break;

                default: throw;
            }
        }

        // Control : Output
        if (isError) {
            cout << "error" << endl;
        } else {
            if (isReversed) { /* 출력시, 배열이 뒤집어진 상태라면 실제로 배열을 뒤집어줌 */
                reverse(nums.begin(), nums.end());
            } string ans;
            /* 출력시 Off-by-one error 를 조심하자 */
            ans.push_back('[');
            if (not(nums.empty())) {
                for (string &num : nums) {
                    ans += num;
                    ans += ",";
                }  ans.pop_back();
            } ans.push_back(']');
            cout << ans << endl;
        }
    }
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글