백준 5430 AC [C++]

작성일 | In |

Problem : AC

유형 : 자료구조(덱)

문제 해석

  • 정해진 규칙대로 구현하라

해결전략

  • R 명령이 들어왔을때마다 Reverse 해주는것은 최악의 경우 100,000^2의 복잡도를 지니게 되어 TLE 가 발생하게 된다.
  • Deque 자료구조를 이용하여 앞뒤에서 원소를 제거하게 했다.

구현

  • 숫자를 파싱 할때, 한자리 수 인지를 확인하였다.
    • 한자리수가 아니면 기존의 숫자에 x10 을 해주고 더해주었다.
  • Deque 자료구조를 이용하여, 실제로 배열을 뒤집진 않고 R 명령인 경우에는 이전 기준 반대 방향을 지우게 구현했다.

주의할점

  • 배열이 비어 있을때 R 하는 것은 에러가 아니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>

using namespace std;

string cmds, inputNums;

void solve(string inputNums) {
    deque<int> numsDeque;

    bool isFirstDigits = true;
    int index = 0;
    for (char num : inputNums) {
        if (num == ',' or num == ']') {
            isFirstDigits = true;
            index++;
        }

        if (!isdigit(num)) continue;
        if (isFirstDigits) {
            isFirstDigits = false;
            numsDeque.push_back(num - '0');
        }
        else {
            numsDeque[index] = numsDeque[index] * 10 + (num - '0');
        }
    }

    bool isReverse = false;

    for (const char &cmd : cmds) {
        if (cmd == 'R') isReverse = !isReverse;	//empty 검사를 하지 않아야 한다.
        else if (cmd == 'D') {
            if (numsDeque.empty()) {
                cout << "error";
                return;
            }
            if (isReverse) numsDeque.pop_back();
            else numsDeque.pop_front();
        }
    }

    if (isReverse) reverse(numsDeque.begin(), numsDeque.end());

    cout << "[";
    for (int i = 0; i < (int)numsDeque.size(); ++i) {
        cout << numsDeque[i];
        if (i != numsDeque.size() - 1) cout << ",";
    }
    cout << "]";
}

void input() {
    int t;  cin >> t;
    while (t--) {
        int n;
        cin >> cmds;
        cin >> n;
        cin >> inputNums;
        solve(inputNums);
        cout << "\n";
    }

}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    input();

    return 0;
}

피드백

  • StringStream 을 잘못 사용하려고 했었다.