[C++] 백준 23294번: 웹 브라우저 1

문제 링크

23294번: 웹 브라우저 1

문제 요약

웹 브라우저가 존재하는데, 이 웹 브라우저는 앞으로 가기, 뒤로 가기, 웹 페이지 접속, 압축 기능이 존재한다.
1. 뒤로 가기 : 뒤로 가기 공간이 비어있지 않다면, 현재 페이지를 앞으로 가기 공간에 저장한다. 뒤로 가기 공간의 마지막 데이터를 현재 페이지로 불러온다.
2. 앞으로 가기 : 앞으로 가기 공간이 비어있지 않다면, 현재 페이지를 뒤로 가기 공간에 저장한다. 앞으로 가기 공간의 마지막 데이터를 현재 페이지로 불러온다.
3. 접속 : 앞으로 가기 공간의 모든 데이터를 삭제한다. 현재 페이지를 뒤로 가기 공간에 넣고 현재 페이지를 갱신한다. 만약 사용하고 있는 캐시가 캐시의 제한량을 넘어서게 된다면 뒤로 가기 공간의 가장 오래된 데이터부터 제한량을 넘지 않을 때까지 삭제한다.
4. 압축 : 뒤로 가기 공간에 연속된 동일한 데이터가 있다면, 하나만 남기고 제거해서 압축한다.
위의 쿼리들을 구현해야 한다.

접근 방법

단순 구현 문제입니다.

문제를 풀기에 앞서 필요한 자료구조를 생각해볼 필요가 있습니다. 삽입은 한쪽에서 일어나지만, 뒤로 가기 작업을 수행할 공간의 경우, 삭제는 앞, 뒤 양쪽에서 일어날 수도 있습니다. 그렇기 때문에 2개의 덱을 활용해서 구현했습니다. 편의 상 두 덱을 '앞으로 가기 덱'과 '뒤로 가기 덱'으로 호칭하도록 하겠습니다. 덱을 두 개 생성하고, 덱 포인터 변수 두 개를 선언해서 각각 연결해줍니다.

1. 앞으로 가기, 뒤로 가기

앞으로 가기와 뒤로 가기는 쓰여 있는대로 구현만 하면 됩니다. 삽입, 삭제 시에 페이지 번호를 덱에 넣어주고, 사용하고 있는 캐시의 크기를 기록할 변수는 별도로 갱신해줘야 합니다.

접속 작업이 일어나면 앞으로 가기 공간의 데이터는 모두 삭제가 됩니다. 그렇기 때문에 접속 작업 이후, 제한된 캐시의 용량을 넘어서서 삭제가 필요한 경우, 앞으로 가기 공간의 크기는 확인할 필요가 없습니다. 뒤로 가기 공간의 크기만 별도의 변수로 체크해주면 됩니다.

앞으로 가기와 뒤로 가기 작업은 새로운 페이지가 추가되는 것이 아니기 때문에, 캐시의 용량 제한에 걸리는지 따로 확인해줄 필요는 없습니다.

2. 접속

만약 최초의 웹 페이지 접속 작업이 시행되는 경우에는, 현재 페이지를 뒤로 가기 덱에 넣으면 안 된다는 점을 주의해서 구현해 주어야 합니다. 현재 페이지는 최초의 웹 페이지 접속 전까지는 비어 있는 상황입니다.

접속 작업에서는 앞으로 가기 덱의 원소들을 모두 삭제하고, 현재 페이지를 뒤로 가기 덱에 넣어줍니다. 캐시 변수도 함께 갱신해줍니다. 그 다음에, 만약 현재 페이지 크기와 뒤로 가기 공간 크기의 합이 캐시의 용량 제한보다 크다면, 합이 작거나 같아질 때까지 덱을 앞에서부터 pop해줘야 합니다.

3. 압축

제 경우에는 압축 기능을 위해서 new 연산자와 포인터를 사용했습니다. 압축을 하기 전, 별도의 포인터 변수를 만들어서 back이 가리키고 있는 덱을 연결해줍니다. 그리고 back은 new 연산자를 통해서 생성된 새로운 덱을 연결해줍니다. 이제 연속해서 같지 않은 경우를 모두 back에 새로이 삽입하면 됩니다. 마지막으로 원래 덱은 delete 해줍니다. 사실 입력의 크기가 작아서 굳이 이렇게 불편하게 구현할 필요는 없었을거 같습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 2001;
int cap[MAX];

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

	int n, q, c;
	cin >> n >> q >> c;

	for (int i = 1; i <= n; i++)
		cin >> cap[i];

	int page = 0, cache = 0;
	deque<int>* back = new deque<int>, * front = new deque<int>;

	while (q--) {
		char work;
		cin >> work;

		switch (work) {
		case 'B':
			if (!back->empty()) {
				front->push_back(page);

				page = back->back();

				cache -= cap[page];
				back->pop_back();
			}

			break;
		case 'F':
			if (!front->empty()) {
				back->push_back(page);
				cache += cap[page];

				page = front->back();

				front->pop_back();
			}

			break;
		case 'A':
			int i;
			cin >> i;

			front->clear();

			cache += cap[page];
			if (page)
				back->push_back(page);
			page = i;

			while (cache + cap[page] > c) {
				cache -= cap[back->front()];
				back->pop_front();
			}

			break;
		case 'C':
			if (back->empty())
				break;

			deque<int>* tmp = back;
			back = new deque<int>;

			cache = cap[tmp->at(0)];
			back->push_back(tmp->at(0));
			for (int i = 1; i < tmp->size(); i++) {
				if (tmp->at(i) != tmp->at(i - 1)) {
					back->push_back(tmp->at(i));
					cache += cap[tmp->at(i)];
				}
			}

			delete tmp;
		}
	}

	cout << page << '\n';

	if (!back->empty()) {
		for (int i = back->size() - 1; i >= 0; i--)
			cout << back->at(i) << ' ';
		cout << '\n';
	}
	else
		cout << -1 << '\n';

	if (!front->empty()) {
		for (int i = front->size() - 1; i >= 0; i--)
			cout << front->at(i) << ' ';
		cout << '\n';
	}
	else
		cout << -1 << '\n';

	delete front, back;
	return 0;
}