[C/C++] 백준 5430번 - AC

✏️  문제 링크

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

 

✏️ 문제 설명

✏️ 로직

값을 재배치하고 빼는 자료구조가 필요하다 , 배열을 뒤집어야 하는 상황이 필요하다

• deque, vector를 떠올림

근데 테스트케이스와 배열연산 함수의 길이와 입력받는 길이를 읽어보니 배열을 뒤집는건 실질적으로 불가능

• 무조건 시간 초과가 발생할 것 같고, 아무리 빨라도 O(n/2)기 때문에 배열을 뒤집으면 안됨
• 즉 뒤집는다 ⇒ 배열의 마지막 부분 or 첫 부분을 가리키게 하면 된다

즉, 위의 상황들을 고려해봤을 때 deque가 적절하다고 판단. isReversed 변수를 이용해서 배열이 뒤집어 진 상태인지 판단하고, deque를 이용해서 가리키는 방향에 따라 배열의 맨 앞값 혹은 마지막 값을 삭제할 수 있음

✏️ 코드

#include<bits/stdc++.h>
using namespace std;

void fun(string p, int n, string arr) {
    deque<int> dq;
    string s = "";

    // 조건 1 : n이 0이라면 error를 출력 후 return
    if (n == -1) {
        // arr에서 숫자만 가져오기
        for (int i = 1; i < arr.length() - 1; i++) {
            if (arr[i] != ',') {
                s += arr[i];
            } else {
                int num = stoi(s);
                dq.push_back(num);
                s = "";
            }
        }
        dq.push_back(stoi(s));
    }
    bool isReversed = false;
    for (int i = 0; i < p.length(); i++) {
        if (p[i] == 'R') {
            // 뒤집기, 반복자를 맨 마지막으로
            if (isReversed) {
                isReversed = false;
            } else {
                isReversed = true;
            }
        } else if (p[i] == 'D') {
            // 버리기
            if (dq.empty()) {
                // 비어있다면 에러 출력 후 종료
                cout << "error" << "\\n";
                return;
            }

            if (isReversed) // 뒤집어져 있는 상태
                dq.pop_back();

            else // 기본적인 상태
                dq.pop_front();
        }
    }

    if (!isReversed) {
        cout << "[";
        for (auto it = dq.begin(); it != dq.end(); it++) {
            cout << *it ;
            if (it != dq.end() - 1)
                cout << ",";
        }
        cout << "]" << "\\n";
    } else {
        cout << "[";
        for (auto it = dq.rbegin(); it != dq.rend(); it++) {
            cout << *it;
            if (it != dq.rend() -1)
                cout << ",";
        }
        cout << "]" << "\\n";
    }
}

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

    int t, n;
    string p, arr;

    cin >> t;
    while (t--) {
        cin >> p >> n >> arr;
        fun(p, n, arr);
    }
}

✏️ 느낀 점

로직 자체는 금방 작성했는데 계속 16퍼에서 오류가 발생하였다.

질문 게시판을 읽어보니 내가 작성한 코드에서 n이 0인 경우에 D가 아닌 R을 입력해도 error가 출력된다는 것을 깨닫고 다시 코드를 짰으나 또 16퍼에서 틀림 → if문에서 ! =를 써야 하는데 ==을 써버림. 다시 수정하니 정답

문제를 조금 더 꼼꼼하게 읽고 코드를 수정한 후에도 확실하게 확인하는 습관을 길러야겠다 자료구조 문제들을 계속 풀고 있는데, 문제를 읽으면 어떤 자료구조를 사용해야 하는지 조금씩 감이 잡히는 것 같다

 

✏️ 결과