[BOJ/Gold 4] 백준 23294 웹 브라우저 1(C++)

문제 링크

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

23294번: 웹 브라우저 1

 

문제

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

사용자가 웹 사이트에 접속하면 컴퓨터의 캐시(cache)공간에 웹페이지 정보가 저장된다. 그리고 뒤로 가기 또는 앞으로 가기 기능을 사용하면 캐시 공간에 저장되어 있던 페이지의 정보를 불러오게 된다. 하지만 캐시 공간은 한정적이기 때문에 무한정 정보를 저장할 수 없다. 그래서 일정 캐시 용량을 초과하게 되면 방문한지 오래된 페이지가 삭제되도록 설계되어 있다. 사용 중인 캐시 용량은 뒤로 가기 공간,앞으로 가기 공간 그리고 현재 접속 중인 페이지가 사용하고 있는 용량의 총합으로 계산된다. 여기에 주헌이가 개발한 웹 브라우저에는 신기한 기능이 있는데, 바로 압축(Compress)이라는 기능이다. 압축 기능은 뒤로 가기 공간에 같은 번호의 페이지가 연속해서 들어있을 때, 이를 하나로 줄일 수 있는 기능이다.

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

• 뒤로 가기를 실행할 경우

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

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

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

• 웹 페이지에 접속할 경우

1. 앞으로 가기 공간에 저장된 페이지가 모두 삭제된다. 페이지들이 차지하고 있던 크기만큼 현재 사용 캐시에서 줄어든다.
2. 현재 페이지를 뒤로 가기 공간에 추가하고, 다음에 접속할 페이지가 현재 페이지로 갱신된다. 접속한 페이지의 용량만큼 현재 사용 캐시 용량에 추가된다. 단, 처음으로 웹페이지에 접속하는 경우라면, 현재 페이지를 뒤로 가기 공간에 추가하지 않는다.
3. 3번 과정은 2번 과정에서 최대 캐시 용량을 초과할 경우에만 실행된다. 뒤로 가기 공간에서 방문한 지 가장 오래된 페이지 하나를 삭제하며, 그 페이지가 차지하고 있던 크기가 현재 사용 캐시 용량에서 줄어든다. 이 과정은 현재 사용 캐시 용량이 최대 캐시 용량보다 작거나 같아질 때까지 여러번 수행될 수 있다.

• 압축을 실행할 경우

1. 뒤로 가기 공간에서 같은 번호의 페이지가 연속해서 2개 이상 등장할 경우, 가장 최근의 페이지 하나만 남기고 나머지는 모두 삭제한다.
2. 삭제된 페이지가 차지하고 있던 용량만큼 현재 사용 캐시에서 줄어든다.

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

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

입력

첫째 줄에 접속할 수 있는 웹페이지의 종류의 수 N, 사용자가 수행하는 작업의 개수 Q 와 최대 캐시 용량 C 이 순서대로 주어진다.(1 ≤ N, Q ≤ 2,000, 1 ≤ C ≤ 200,000)

둘째 줄에는 N개의 정수 CAPi 가 주어진다. i 는 웹페이지의 번호이며, i 번째 숫자는 i 번째 웹페이지를 방문할 때 사용하는 캐시 공간의 크기를 의미한다. 각 캐시 공간의 크기는 1 ≤ CAPi  ≤ C  를 만족한다.

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

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

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

출력

3줄에 걸쳐서 출력한다.

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

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

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

예제 입력 1

3 11 20
4 5 6
B
F
A 1
A 1
A 2
A 3
B
A 1
A 1
A 2
C

예제 출력 1

2
1 2
-1

예제 입력 2

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

예제 출력 2

2
1
2 2

예제 입력 3

3 8 18
4 5 6
A 1
A 2
A 1
A 2
C
B
A 3
A 1

예제 출력 3

1
3 1
-1

노트

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

파란색 도형 안에 괄호 밖 숫자는 페이지의 번호를, 괄호 안 숫자는 해당 페이지가 사용하는 캐시 공간의 크기이다.

알고리즘 분류

• 구현
• 덱

풀이

각 공간마다 최신 페이지, 가장 오래 된 페이지를 삭제하는 작업을 위해 덱을 사용해야 한다는 것을 바로 떠올릴 수 있다. 양 끝의 원소를 관리할 수 있는 자료구조로 스택과 큐는 부적합하기 때문이다.

B, F, A는 시키는 대로 하면 되며, C에서는 연속해서 중복되는 페이지를 제거하기 위해 큐의 원소를 잠깐 벡터로 옮긴다. 그리고 erase() 함수를 사용하여 연속해서 중복되는 숫자를 제거해준 후 다시 큐로 옮긴다. 이 과정에서 캐시 용량의 총합은 당연히 관리해줘야 한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <deque>
#include <algorithm>
#define FASTIO cin.tie(0); cout.tie(0);
#define MAX 16

using namespace std;
int N, Q, C, I;
vector<int> CAP;
deque<int> BACK_SPACE;
deque<int> FRONT_SPACE;
int NOW_PAGE;
int Cur_Cap = 0;

void compressing() {
    vector<int> Vec;
    while (!BACK_SPACE.empty()) {
        int Back_Page = BACK_SPACE.back();
        Cur_Cap -= CAP[Back_Page - 1];
        BACK_SPACE.pop_back();
        Vec.push_back(Back_Page);
    };
    Vec.erase(unique(Vec.begin(), Vec.end()), Vec.end());
    for (int i = 0; i < Vec.size(); i++) {
        BACK_SPACE.push_front(Vec[i]);
        Cur_Cap += CAP[Vec[i] - 1];
    }
}

void input() {
    cin >> N >> Q >> C;
    for (int i = 0; i < N; i++) {
        int A;
        cin >> A;
        CAP.push_back(A);
    }
    while (Q--) {
        char Cmd;
        cin >> Cmd;
        if (Cmd == 'B') {
            if (!BACK_SPACE.empty()) {
                int Back_Page = BACK_SPACE.front();
                BACK_SPACE.pop_front();
                FRONT_SPACE.push_back(NOW_PAGE);
                NOW_PAGE = Back_Page;
            }
        }
        else if (Cmd == 'F') {
            if (!FRONT_SPACE.empty()) {
                int Front_Page = FRONT_SPACE.back();
                FRONT_SPACE.pop_back();
                BACK_SPACE.push_front(NOW_PAGE);
                NOW_PAGE = Front_Page;
            }
        }
        else if (Cmd == 'A') {
            cin >> I;
            while (!FRONT_SPACE.empty()) {
                int Front_Page = FRONT_SPACE.front();
                FRONT_SPACE.pop_front();
                Cur_Cap -= CAP[Front_Page - 1];
            };
            if (NOW_PAGE == 0) {
                NOW_PAGE = I;
                Cur_Cap += CAP[NOW_PAGE - 1];
            }
            else {
                BACK_SPACE.push_front(NOW_PAGE);
                NOW_PAGE = I;
                Cur_Cap += CAP[NOW_PAGE - 1];
            }
            while (Cur_Cap > C) {
                int Back_Page = BACK_SPACE.back();
                BACK_SPACE.pop_back();
                Cur_Cap -= CAP[Back_Page - 1];
            };
        }
        else if (Cmd == 'C') {
            compressing();
        }
    };
}

void find_Answer() {
    cout << NOW_PAGE << "\n";
    if (BACK_SPACE.empty()) {
        cout << -1 << "\n";
    }
    else {
        while (!BACK_SPACE.empty()) {
            cout << BACK_SPACE.front() << " ";
            BACK_SPACE.pop_front();
        };
        cout << "\n";
    }
    if (FRONT_SPACE.empty()) {
        cout << -1 << "\n";;
    }
    else {
        while (!FRONT_SPACE.empty()){
            cout << FRONT_SPACE.back() << " ";
            FRONT_SPACE.pop_back();
        }
        cout << "\n";
    }
}

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

    return 0;
}