백준 23300 - 웹 브라우저 2 (C++)

문제 https://www.acmicpc.net/problem/23300

23300번: 웹 브라우저 2

 

풀이

덱을 이용해서 풀이하는 구현 문제이다.

문제 설명대로 차근차근 코드를 작성하면 해결할 수 있다.

뒤로 가기, 앞으로 가기 공간을 구현할 때 스택 대신 덱을 사용했는데, 압축 실행시 인덱스로 접근하고 싶었기 때문이다.

그리고 압축 실행시, 뒤로 가기 공간이 비어있으면 out of bounds 오류가 발생하므로, 먼저 비어있는지부터 확인해야 한다.

 

코드

#include <iostream>
#include <deque>

using namespace std;

deque<int> Backstack;
deque<int> Frontstack;
int curP;

void Back() {
    if (Backstack.empty()) return;
    Frontstack.push_front(curP);
    curP = Backstack.front();
    Backstack.pop_front();
}

void Front() {
    if (Frontstack.empty()) return;
    Backstack.push_front(curP);
    curP = Frontstack.front();
    Frontstack.pop_front();
}

void Access(int page) {
    if (!Frontstack.empty()) Frontstack.clear();
    if (curP != 0) {
        Backstack.push_front(curP);
    }
    curP = page;
}

void Compress() {
    if (Backstack.empty()) return;
    int idx = 0;
    while (1) {
        if (idx + 1 == Backstack.size()) break;
        if (Backstack[idx] == Backstack[idx + 1]) {
            Backstack.erase(Backstack.begin() + idx + 1);
        } else idx++;
    }

}

int main() {
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        char C;
        cin >> C;
        if (C == 'B') Back();
        else if (C == 'F') Front();
        else if (C == 'A') {
            int p;
            cin >> p;
            Access(p);
        } else Compress();
    }
    cout << curP << '\n';
    if (Backstack.empty()) cout << "-1\n";
    else {
        for (int i = 0; i < Backstack.size(); i++) {
            cout << Backstack[i] << " ";
        }
        cout << '\n';
    }
    if (Frontstack.empty()) cout << "-1\n";
    else {
        for (int i = 0; i < Frontstack.size(); i++) {
            cout << Frontstack[i] << " ";
        }
    }
}