[BOJ/5430/C++] AC

👀 문제

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

 

 

[문제 요약]

• R: 배열 뒤집기
• D: 첫번째 수 버리기 (비어있는데 D할 경우는 error 출력)

---

📝 접근 방법

뒤집지 않으면 앞에서 빼야하고, 뒤집은 형태면 뒤에서 빼야하니까 deque 자료구조를 사용하였다.

우선 배열의 값이 [, , ,] 형태의 String으로 들어와서 이 배열에서 값만 빼고, 그거를 int로 바꾸면서 deque에 넣어주는 배열 전처리 함수 (preprocess)를 만들었다.

deque<int> preprocess(int n, const string& StringArr) {
    deque<int> dq;
    string tmp;

    for (int i = 1; i < StringArr.size(); i++) {
        char c = StringArr[i];

        if (isdigit(c) == true) {
            tmp += c;
        } else if (((c == ',') || (c == ']')) && !tmp.empty()) {
            dq.push_back(stoi(tmp));
            tmp.clear();
        }
    }
    return dq;
}

 

받아온 StringArr을 돌면서 숫자로 변환이 가능하면 우선 tmp에 집어넣고, 값이 끊기는 , 또는 ] 이 들어오면 그때 tmp에 있는 값을 int로 바꿔서 deque에 넣어주는 함수이다.

 

 

첫번째 시도 -> 시간 초과

void sol(string p, deque<int> dq) {
    for (char c: p) {
        if (c == 'D') {                 // D: 첫번째 수 버리기 (비어있으면 에러 출력하고 끝)
            if (dq.empty() == true) {
                cout << "error\n";
                return;
            } else {
                dq.pop_front();
            }
        } else if (c == 'R') {         // R: 배열에 있는 수 뒤집기
            reverse(dq.begin(), dq.end());
        }
    }

    cout << "[";
    for (size_t i = 0; i < dq.size(); ++i) {
        if (i > 0) cout << ",";
        cout << dq[i];
    }
    cout << "]\n";
}

 

D가 들어왔을 때

• 비어있는지 확인
  • 비어있으면: error를 출력하면서 끝
  • 비어있지 않으면: 첫번째 수를 제거하는 pop_front()를 해준다.

R이 들어왔을 때

• reverse()를 이용하여 deque를 진짜 뒤집었다.

=> '시간초과' 발생

 

 

두번째 시도 -> 성공

R 연산이 매번 reverse()를 통해서 전체 deque를 뒤집는 것 때문에 시간 초과가 발생하였다.

reverse()의 시간 복잡도는 O(N)으로 R 이 반복될 경우에는 최대 O(10^5 X 10^5)가 되어 시간초과가 난 것이다.

// 문제 해결
void sol(string p, deque<int> dq) {
    bool isReversed = false;

    for (char c: p) {
        if (c == 'D') {                 // D: 첫번째 수 버리기 (비어있으면 에러 출력하고 끝)
            if (dq.empty() == true) {
                cout << "error\n";
                return;
            } else {
                if (isReversed == false) {
                    dq.pop_front();
                } else
                    dq.pop_back();
            }
        } else if (c == 'R') {         // R: 배열에 있는 수 뒤집기
            isReversed = !isReversed;
        }
    }

    // 출력하기 
    cout << "[";

    if (isReversed == false) {          // 안 뒤집혔을 경우
        while (dq.size() > 1) {
            cout << dq.front() << ',';
            dq.pop_front();
        }
        if (!dq.empty()) {
            cout << dq.front();
        }

    } else {                            // 뒤집혔을 경우
         while (dq.size() > 1) {
            cout << dq.back() << ',';
            dq.pop_back();
         }
         if (!dq.empty()) {
            cout << dq.back();
         }
    }
    cout << "]\n";
}

 

R 명령이 나올 때마다 실제로 reverse()를 사용하지 않고 뒤집혔는지를 체크하는 isReversed 플래그를 이용하였다.

만약 뒤집히지 않은 (isReversed = false) 상태이면 D명령이 나왔을 때 앞에서 제거하고,

뒤집힌 상태(isReversed = true) 이면 뒤에서 제거하면 되기 때문이다.

---

😎 해결 코드

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

// 배열 전처리
deque<int> preprocess(int n, const string& StringArr) {
    deque<int> dq;
    string tmp;

    for (int i = 1; i < StringArr.size(); i++) {
        char c = StringArr[i];

        if (isdigit(c) == true) {
            tmp += c;
        } else if (((c == ',') || (c == ']')) && !tmp.empty()) {
            dq.push_back(stoi(tmp));
            tmp.clear();
        }
    }
    return dq;
}

// 문제 해결
void sol(string p, deque<int> dq) {
    bool isReversed = false;

    for (char c: p) {
        if (c == 'D') {                 // D: 첫번째 수 버리기 (비어있으면 에러 출력하고 끝)
            if (dq.empty() == true) {
                cout << "error\n";
                return;
            } else {
                if (isReversed == false) {
                    dq.pop_front();
                } else
                    dq.pop_back();
            }
        } else if (c == 'R') {         // R: 배열에 있는 수 뒤집기
            isReversed = !isReversed;
        }
    }

    // 출력하기 
    cout << "[";

    if (isReversed == false) {          // 안 뒤집혔을 경우
        while (dq.size() > 1) {
            cout << dq.front() << ',';
            dq.pop_front();
        }
        if (!dq.empty()) {
            cout << dq.front();
        }

    } else {                            // 뒤집혔을 경우
         while (dq.size() > 1) {
            cout << dq.back() << ',';
            dq.pop_back();
         }
         if (!dq.empty()) {
            cout << dq.back();
         }
    }
    cout << "]\n";
}

int main(void) {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    int T; cin >> T;

    for (int i=0; i < T; i++) {
        string p; cin >> p;                     // 함수 p
        int n; cin >> n;                        // 배열에 있는 수의 개수
        string StringArr; cin >> StringArr;     // 배열 입력

        deque<int> dq = preprocess(n, StringArr);
        sol(p, dq);
    }

    return 0;
}

 

---

⚠️ 틀리거나 시간이 오래 걸린 이유

reverse()를 사용하여서 시간 초과가 발생하였다.

---

📚 배운 점

isdigit()

: 문자를 다룰 때 숫자인지를 판단할 수 있는 함수이다.

• 헤더: #include <cctype>
• int isdigit(int c);
  • 매개변수로 들어온 char 타입이 10진수 숫자로 변경이 가능하면 true, 아니면 false를 반환

 

참고 자료

https://cplusplus.com/reference/cctype/isdigit/?kw=isdigit