백준 웹 브라우저1 [c++]
23294 웹 브라우저1 골드4
문제 링크 APC 2021 3번
문제
우리는 웹 페이지에 접속할 때 ‘웹 브라우저’를 사용한다. 웹 브라우저에는 크게 뒤로 가기(Backward), 앞으로 가기(Frontward), 웹페이지 접속(Access) 기능이 있다.
사용자가 웹 사이트에 접속하면 컴퓨터의 캐시(cache)공간에 웹페이지 정보가 저장된다. 그리고 뒤로 가기 또는 앞으로 가기 기능을 사용하면 캐시 공간에 저장되어 있던 페이지의 정보를 불러오게 된다. 하지만 캐시 공간은 한정적이기 때문에 무한정 정보를 저장할 수 없다. 그래서 일정 캐시 용량을 초과하게 되면 방문한지 오래된 페이지가 삭제되도록 설계되어 있다. 사용 중인 캐시 용량은 뒤로 가기 공간,앞으로 가기 공간 그리고 현재 접속 중인 페이지가 사용하고 있는 용량의 총합으로 계산된다. 여기에 주헌이가 개발한 웹 브라우저에는 신기한 기능이 있는데, 바로 압축(Compress)이라는 기능이다. 압축 기능은 뒤로 가기 공간에 같은 번호의 페이지가 연속해서 들어있을 때, 이를 하나로 줄일 수 있는 기능이다.
각 기능의 작동방식은 각각 다음과 같다.
뒤로 가기를 실행할 경우 뒤로 가기 공간에 1개 이상의 페이지가 저장되어 있을 때만 2,3번 과정이 실행된다. 0개일 때 이 작업은 무시된다. 현재 보고 있던 웹페이지를 앞으로 가기 공간에 저장한다. 뒤로 가기 공간에서 방문한지 가장 최근의 페이지에 접속한다. 그리고 해당 페이지는 뒤로 가기 공간에서 삭제된다. 앞으로 가기를 실행할 경우 앞으로 가기 공간에 1개 이상의 페이지가 저장되어 있을 때만 2,3번 과정이 실행된다. 0개일 때 이 작업은 무시된다. 현재 보고 있던 페이지를 뒤로 가기 공간에 저장한다. 앞으로 가기 공간에서 방문한지 가장 최근의 페이지에 접속한다. 그리고 해당 페이지는 앞으로 가기 공간에서 삭제된다. 웹 페이지에 접속할 경우 앞으로 가기 공간에 저장된 페이지가 모두 삭제된다. 페이지들이 차지하고 있던 크기만큼 현재 사용 캐시에서 줄어든다. 현재 페이지를 뒤로 가기 공간에 추가하고, 다음에 접속할 페이지가 현재 페이지로 갱신된다. 접속한 페이지의 용량만큼 현재 사용 캐시 용량에 추가된다. 단, 처음으로 웹페이지에 접속하는 경우라면, 현재 페이지를 뒤로 가기 공간에 추가하지 않는다. 3번 과정은 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을 출력한다.
풀이
브라우저에서 앞으로, 뒤로, 접속, 압축에 따라 cache를 처리하는 문제.
뒤로가기 공간(back cache)과 앞으로가기 공간(front cache)가 필요하고 현재 접속중인 페이지는 하나기 때문에 int.
Case
- 앞으로가거나 뒤로가는 경우에서는 페이지의 공간의 이동만 일어나지 cache에는 변화 없다.
- 접속할 경우 front cache를 비워 cache감소, 그리고 현재 페이지를 back cache로 이동 & 새로운 현재 페이지 설정, 그리고 만약 back cache가 초과한다면 오래된 순으로 삭제.
- 압축할 경우 back cache의 중복인 페이지를 제거하면 된다.
구현을 위해 front cache와 back cache는 vector를 사용했다.
case 1은 조건에 맞게 push와 pop으로 구현하면 됨.
case 2는 우선 front cache에 있는 페이지(크기)만큼 cache를 줄여주고 front cache를 비운다.
그리고 now에 현재 페이지를 설정하고,
back cache가 초과할 경우 가장 오래된 것이 삭제되어야 하기 때문에(vector 구조를 사용했기 때문에)
erase(bachC.begin())처럼 begin과 erase를 사용해 맨 앞의 요소를 삭제한다.
case 3은 우선 현재 cache에서 back cache에 있는 페이지(크기)만큼 cache를 줄여주고,(1)
erase와 unique를 사용해 중복된 요소를 제거해준다.(2)
그리고 다시 back cache에 있는 페이지(크기)만큼 cache를 늘려주면 중복된 것만큼 cache가 줄어들게 된다. (3)
초기 cache : 15, backCache : {1,2,3,2,2}
case 3 과정
(1) ==> cache : 5 (-10), backCache : {1,2,3,2,2}
(2) ==> cache : 5 (0), backCache : {1,2,3}
(3) ==> cache : 11 (+6), backCache : {1,2,3}
결과 ==> 중복된 {2,2} 만큼(4만큼) cache가 줄어듦.
이후 출력 조건에 맞게 출력해주면 된다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
int n, q, c;
int usedCache = 0;
int cap[2001];
vector<int> backC;
vector<int> frontC;
int now = 0;
int main()
{
cin >> n >> q >> c;
for(int i = 1; i <= n; i++)
{
cin >> cap[i];
}
for(int i = 0; i < q; i++)
{
string act;
cin >> act;
if(act.compare("B") == 0){
if(!backC.empty()){
if(now >= 1 && now <= 2000){
frontC.push_back(now);
now = backC.back();
backC.pop_back();
}
}
}
if(act.compare("F") == 0){
if(!frontC.empty()){
if(now >= 1 && now <= 2000){
backC.push_back(now);
now = frontC.back();
frontC.pop_back();
}
}
}
if(act.compare("A") == 0)
{
int index;
cin >> index;
int used = 0;
for(int i = 0; i < frontC.size(); i++)
{
used += cap[frontC[i]];
}
usedCache -= used;
if(usedCache < 0){
usedCache = 0;
}
frontC.clear();
if(now != 0)
{
backC.push_back(now);
}
now = index;
usedCache += cap[now];
while(usedCache > c && !backC.empty()){
usedCache -= cap[backC.front()];
backC.erase(backC.begin());
}
}
if(act.compare("C") == 0){
if(!backC.empty()){
for(int i = 0; i < backC.size(); i++)
{
usedCache -= cap[backC[i]];
}
backC.erase(unique(backC.begin(), backC.end()), backC.end());
for(int i = 0; i < backC.size(); i++)
{
usedCache += cap[backC[i]];
}
if(usedCache < 0)
{
usedCache = 0;
}
}
}
}
cout << now << endl;
if(backC.empty()){
cout << -1 << endl;
} else{
reverse(backC.begin(), backC.end());
for(int i = 0; i < backC.size(); i++)
{
cout << backC[i] << " ";
}
cout << "\n";
}
if(frontC.empty()){
cout << -1 << endl;
} else{
reverse(frontC.begin(), frontC.end());
for(int i = 0; i < frontC.size(); i++)
{
cout << frontC[i] << " ";
}
cout << "\n";
}
return 0;
}