백준 5430번 [AC](C++) -yes6686- 티스토리

백준 문제 풀이: 5430 [AC]

---

문제 링크: https://www.acmicpc.net/problem/5430

문제 설명:

주어진 R(뒤집기)와 D(버리기) 연산을 사용하여 배열을 조작합니다. 배열이 비어 있는 상황에서 D를 호출하거나 유효하지 않은 연산이 발생하면 "error"를 출력해야 합니다. 최종 배열의 상태를 출력하세요.

입력 조건:

• 첫 번째 줄에 테스트 케이스의 개수 T가 주어집니다. (1 ≤ T ≤ 100)
• 각 테스트 케이스마다:
  • 수행할 함수 p (최대 100,000자)
  • 배열의 크기 n (0 ≤ n ≤ 100,000)
  • 배열 x가 주어집니다. (x는 대괄호로 감싸져 있으며, 각 숫자는 최대 100)

출력 조건:

• 각 테스트 케이스에 대해 결과 배열 또는 "error"를 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <deque>
#include <string>
using namespace std;

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

    int T;
    cin >> T;

    while (T--) {
        string p, arr;
        int n;
        cin >> p >> n >> arr;

        deque<int> d;
        string num = "";
        for (int i = 1; i < arr.size(); i++) { // 배열 파싱
            if (arr[i] == ',' || arr[i] == ']') {
                if (!num.empty()) {
                    d.push_back(stoi(num));
                    num = "";
                }
            } else if (isdigit(arr[i])) {
                num += arr[i];
            }
        }

        bool reversed = false, error = false;

        for (char cmd : p) {
            if (cmd == 'R') {
                reversed = !reversed; // 뒤집기 상태 전환
            } else if (cmd == 'D') {
                if (d.empty()) {
                    error = true; // 비어 있는 배열에서 D 연산 시 에러 발생
                    break;
                }
                if (reversed) {
                    d.pop_back();
                } else {
                    d.pop_front();
                }
            }
        }

        if (error) {
            cout << "error\n";
        } else {
            cout << "[";
            while (!d.empty()) {
                if (reversed) {
                    cout << d.back();
                    d.pop_back();
                } else {
                    cout << d.front();
                    d.pop_front();
                }
                if (!d.empty()) cout << ",";
            }
            cout << "]\n";
        }
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 `deque` 자료구조를 활용하여 배열을 효율적으로 조작합니다.

• 입력 처리:
  • 배열 파싱: 주어진 배열 문자열에서 숫자를 추출하여 `deque`에 저장합니다.
• 명령 처리:
  • `R`: 뒤집기 상태를 `reversed` 변수로 관리합니다.
  • `D`: 배열의 앞 또는 뒤에서 원소를 제거합니다. 배열이 비어 있는 경우 "error"를 출력합니다.
• 결과 출력:
  • `deque`의 내용을 출력하며 뒤집기 상태에 따라 앞이나 뒤에서 접근합니다.

시간 복잡도 분석:

• 배열 파싱: O(n).
• 명령 처리: O(p), p는 함수의 길이.

전체 시간 복잡도는 O(T × (n + p))이며, 입력 제한 내에서 효율적으로 처리할 수 있습니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
2
RDD
4
[1,2,3,4]
DD
1
[42]

출력:
[2,1]
error

주어진 명령에 따라 배열이 올바르게 조작되고 결과가 출력됩니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!