[백준] 5430: AC

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

5430번: AC

문제만 읽으면 아주 간단한 구현 문제로 보인다. 하지만 생각보다 정답율이 약 19%밖에 되지 않아 의문을 가졌는데 풀다보면 조금은 알게 된다.

여기서 주의해야하는 함정 포인트는 크게 2가지가 있다.

 

1) R, D로 뒤집고 지우라는 명령을 곧이 곧대로 받아들이면 안된다.

코드만 봅면 지우거나 뒤집는 게 쉬워보이지만, 메모리 상에서는 상당히 귀찮은 일이다. 시간복잡도가 O(N)이나 소요되는 일이다.

따라서 뒤집기(R) 처리는 하나의 변수를 지정하여 현재 배열을 앞에서부터 접근하는지, 뒤에서부터 접근하는지를 기록하면 해당 변수만 바꾸어주면 되기 때문에 상당히 간편해진다. 그리고 지우기(D) 처리는 앞뒤 인덱스를 두고 조절하면 된다. 시작 인덱스는 0, 끝 인덱스는 배열의 크기 - 1로 초기화한다. 그리고 앞에서 요소를 지웠으면 앞 인덱스를 1씩 추가하고, 끝에서 요소를 지웠으면 뒤 인덱스를 1씩 감소한다.

이러면 배열을 실제로 뒤집거나 지우는 것은 아니지만 시뮬레이션할 수 있게 된다. 이렇게 하는 것이 훨씬 효율적이다.

 

2) 배열을 다룰 때는 항상 인덱스 주의(Out of Bounds가 싫어요)

위 1번 방법대로 하면 배열을 잘못 접근하는 일을 훨씬 줄어든다. 그런데 내가 간과했던 점은 배열에 요소가 아예 없는 경우를 간과했다.

배열에 요소가 아예 없다거나 뒤집기 처리는 문제가 안된다. 그냥 []을 출력하면 된다.

하지만 빈 배열에서 지우기를 시도하면 그제서야 에러를 뱉어내야 한다.

 

ex1)

D

1

[12]

👉 []

 

ex 2)

D

0

[]

👉 error

 

그런데 마지막 원소를 제거하게 되면 front의 idx - back의 idx =1이 된다는 점에 유의해야 한다.

그리고 제거할 때 인덱스를 조정하기 전에 error 여부를 판단하는 것이 논리적으로 올바르다.

 

문자열 파싱하는 것도 이번에 꽤 까다로웠다.

istringstream, buffer을 사용해 쉼표를 기준으로 string을 split 해주었다.

while(getline(iss, buffer, ','))

그리고 가장 자주 쓰이는 문자열 파싱함수인 substr 함수도 이번 기회에 재확인하였다.

// pos ~ 문자열 끝
string.substr(pos);
// pos부터 num 길이의 문자열 파싱
string.substr(pos, num);

 

전체 코드는 다음과 같다.

#include <iostream>
#include <cstring>
#include <vector>
#include <sstream>
using namespace std;
vector<int> arr(100001);

/**
 * https://www.acmicpc.net/board/view/25456
 */

void parse_arr(string cmd) {
    int num;
    string str = cmd.substr(1);
    str = str.substr(0, str.length() - 1);
    istringstream iss;
    iss.str(str);
    iss.seekg(0);
    string buffer;
    while(getline(iss, buffer, ',')) {
        num = stoi(buffer);
        arr.push_back(num);
    }
}
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    // true이면 0부터 접근
    // false이면 reverse
    cin >> t;
    while(t--) {
        string cmd, str_arr;
        int n;
        bool is_front, is_error = false;
        int front_idx = 0, tail_idx = 0;
        cin >> cmd;
        cin >> n;
        cin >> str_arr;

        // 초기화
        arr.clear();
        parse_arr(str_arr);
        is_front = true;
        front_idx = 0;
        tail_idx = arr.size() - 1;
        for(auto c: cmd) {
            if(c == 'R'){
                is_front = !is_front;
            }
            else if(c == 'D') {
                if(is_front) {
                    if(front_idx > tail_idx) {
                        is_error = true;
                        cout << "error" << endl;
                        break;
                    }
                    front_idx++;
                }
                // 뒤에서부터 접근
                else {
                    if(front_idx > tail_idx) {
                        is_error = true;
                        cout << "error" << endl;
                        break;
                    }
                    tail_idx--;
                }
            }
        }

        if(!is_error) {
            cout << '[';
            if(is_front) {
                for(int i = front_idx; i <= tail_idx;i++) {
                    cout << arr[i];
                    if(i != tail_idx) cout << ',';
                }
            }
            else {
                for(int i = tail_idx;i >= front_idx;i--) {
                    cout << arr[i];
                    if(i != front_idx) cout << ',';
                }
            }
            cout << ']' << endl;
        }

    }
}