[BOJ/Gold 5] 백준 23300 웹 브라우저 2(C++)

문제 링크

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

23300번: 웹 브라우저 2

문제

우리는 웹 페이지에 접속할 때 '웹 브라우저'를 사용한다. 웹 브라우저에는 크게 뒤로 가기(Backward), 앞으로 가기(Frontward), 웹페이지 접속(Access) 기능이 있다.

사용자가 웹 사이트에 접속하면 컴퓨터의 캐시(cache)공간에 웹페이지 정보가 저장된다. 그리고 뒤로 가기 또는 앞으로 가기 기능을 사용하면 캐시 공간에 저장되어 있던 페이지의 정보를 불러오게 된다. 여기에 주헌이가 개발한 웹 브라우저에는 신기한 기능이 있는데, 바로 압축(Compress)이라는 기능이다. 압축 기능은 뒤로 가기 공간에 같은 번호의 페이지가 연속해서 들어있을 때, 이를 하나로 줄일 수 있는 기능이다.

각 기능의 작동방식은 각각 다음과 같다.

• 뒤로 가기를 실행할 경우

1. 뒤로 가기 공간에 1개 이상의 페이지가 저장되어 있을 때만 2,3번 과정이 실행된다. 0개일 때 이 작업은 무시된다.
2. 현재 보고 있던 웹페이지를 앞으로 가기 공간에 저장한다.
3. 뒤로 가기 공간에서 방문한지 가장 최근의 페이지에 접속한다. 그리고 해당 페이지는 뒤로 가기 공간에서 삭제된다.

• 앞으로 가기를 실행할 경우

1. 앞으로 가기 공간에 1개 이상의 페이지가 저장되어 있을 때만 2,3번 과정이 실행된다. 0개일 때 이 작업은 무시된다.
2. 현재 보고 있던 페이지를 뒤로 가기 공간에 저장한다.
3. 앞으로 가기 공간에서 방문한지 가장 최근의 페이지에 접속한다. 그리고 해당 페이지는 앞으로 가기 공간에서 삭제된다.

• 웹 페이지에 접속할 경우

1. 앞으로 가기 공간에 저장된 페이지가 모두 삭제된다.
2. 현재 페이지를 뒤로 가기 공간에 추가하고, 다음에 접속할 페이지가 현재 페이지로 갱신된다. 단, 처음으로 웹페이지에 접속하는 경우라면 현재 페이지를 뒤로 가기 공간에 추가하지 않는다.

• 압축을 실행할 경우

1. 뒤로 가기 공간에서 같은 번호의 페이지가 연속해서 2개 이상 등장할 경우, 가장 최근의 페이지 하나만 남기고 나머지는 모두 삭제한다.

Q개의 작업을 모두 마친 뒤에 현재 접속 중인 페이지와 뒤로 가기 공간, 앞으로 가기 공간에 저장되어 있는 페이지의 번호를 구하여라.

초기 상태에는 뒤로가기 공간, 앞으로 가기 공간이 모두 비어있으며 어떤 페이지에도 접속해있지 않는 상태이다. 또한 같은 번호의 페이지에 여러번 접속할 수 있으며, 그럴 경우 같은 번호의 페이지이라도 방문 순서는 각기 다르게 취급된다. 이 문제에서 컴퓨터의 캐시 용량은 충분히 크다고 가정한다.

입력

첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 가 각각 주어진다.(1 ≤ N, Q ≤ 2,000)

둘째 줄부터는 Q개의 작업이 주어지며, 각 작업이 의미하는 바는 다음과 같다.

• B : 뒤로 가기를 실행한다.
• F : 앞으로 가기를 실행한다.
• A i : i 번 웹페이지에 접속한다.
• C : 압축을 실행한다.

A(접속)작업이 적어도 한 번은 등장한다.

출력

3줄에 걸쳐서 출력한다.

첫째 줄에는 현재 접속 중인 페이지의 번호를 출력한다.

둘째 줄에는 뒤로 가기 공간에서 가장 최근에 방문한 순서대로 페이지의 번호를 출력한다. 저장된 페이지가 없다면 -1 을 출력한다.

셋째 줄에는 앞으로 가기 공간에서 가장 최근에 방문한 순서대로 페이지의 번호를 출력한다. 저장된 페이지가 없다면 -1 을 출력한다.

예제 입력 1

3 11
B
F
A 1
A 1
A 2
A 3
B
A 1
A 1
A 2
C

예제 출력 1

2
1 2 1
-1

예제 입력 2

2 8
A 1
A 1
A 2
A 2
A 2
B
B
C

예제 출력 2

2
1
2 2

예제 입력 3

3 8
A 1
A 2
A 1
A 2
C
B
A 3
A 1

예제 출력 3

1
3 1 2 1
-1

노트

아래 그림은 에제 입력 1을 나타내고 있다.

파란색 도형 안에 숫자는 페이지의 번호를 나타내고 있다.

알고리즘 분류

• 구현
• 자료 구조

풀이

먼저 뒤로 가기 공간, 앞으로 가기 공간에 해당하는 덱 2개를 선언하고 현재 접속한 페이지를 나타내는 변수 1개를 선언한다.

그리고 4가지의 작업을 다음과 같이 수행한다.

• 뒤로 가기
  • 뒤로 가기 공간이 비어있지 않다면, 현재 페이지를 덱의 back으로 초기화하고 덱을 한 번 pop_back한다.
  • 뒤로 가기 공간이 비어있다면 아무것도 하지 않는다.
• 앞으로 가기
  • 앞으로 가기 공간이 비어있지 않다면, 현재 페이지를 덱의 front로 초기화하고 덱을 한 번 pop_front한다.
  • 앞으로 가기 공간이 비어있다면 아무것도 하지 않는다.
• 웹 페이지 접속
  • 앞으로 가기 공간을 clear한 후, 현재 페이지를 뒤로 가기 공간에 push_back하고 현재 페이지를 I로 초기화한다.
  • 처음 웹 페이지에 접속하는 경우라면 그냥 현재 페이지를 I로 초기화한다.
• 압축
  • 새로운 덱을 선언하고, 뒤로 가기 공간의 앞에서부터 원소를 새로운 덱에 push_back하며 다음 push할 원소와 비교해서 일치한다면 그냥 push하지 않고 뒤로 가기 공간만 pop_front한다.
  • 뒤로 가기 공간이 빌 때까지 작업을 수행하며 작업이 끝나면 뒤로 가기 공간을 새로운 덱으로 초기화시킨다.

마지막으로 현재 페이지를 출력하고, 다음 줄에는 뒤로 가기 공간에 있는 페이지들을 뒤에서부터 출력하고, 마지막 줄에는 앞으로 가기 공간에 있는 페이지들을 앞에서부터 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <algorithm>
#define MAX 10001
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, Q, I;
char C;
deque<int> DQ[2];
int Now_Page = -1;

void input() {
    cin >> N >> Q;
    while (Q--) {
        cin >> C;
        if (C == 'B'){
            if (!DQ[0].empty()) {
                DQ[1].push_front(Now_Page);
                Now_Page = DQ[0].back();
                DQ[0].pop_back();
            }
        }
        else if (C == 'F') {
            if (!DQ[1].empty()) {
                DQ[0].push_back(Now_Page);
                Now_Page = DQ[1].front();
                DQ[1].pop_front();
            }
        }
        else if (C == 'A') {
            cin >> I;
            if (Now_Page != -1) {
                DQ[1].clear();
                DQ[0].push_back(Now_Page);
            }
            Now_Page = I;
        }
        else if (C == 'C') {
            deque<int> New;
            while (!DQ[0].empty()) {
                if (New.empty()) {
                    New.push_back(DQ[0].front());
                    DQ[0].pop_front();
                }
                else {
                    if (New.back() != DQ[0].front()) {
                        New.push_back(DQ[0].front());
                    }
                    DQ[0].pop_front();
                }
            };
            DQ[0] = New;
        }
    };
}

void find_Answer() {
    cout << Now_Page << "\n";
    if (DQ[0].empty()) {
        cout << "-1";
    }
    else {
        while (!DQ[0].empty()) {
            cout << DQ[0].back() << " ";
            DQ[0].pop_back();
        };
    }
    cout << "\n";
    if (DQ[1].empty()) {
        cout << "-1";
    }
    else {
        while (!DQ[1].empty()) {
            cout << DQ[1].front() << " ";
            DQ[1].pop_front();
        };
    }
    cout << "\n";
}

int main() {
    FASTIO
    input();
    find_Answer();

    return 0;
}