[Baekjoon] 23294_웹 브라우저 1

Gold IV

문제(출처: https://www.acmicpc.net/problem/23294)

---

< 웹 브라우저 1 >

 

문제 풀이 

 

Deque 2개를 사용해서 뒤로 가기 공간과 앞으로 가기 공간을 나누어 구현했다.

각 작업을 실행할 때마다 캐시 용량도 뒤로 가기 공간과 앞으로 가기 공간을 나누어 계산해 주었다.

 

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.StringTokenizer;

public class _23294_ { // 웹 브라우저 1

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int q = Integer.parseInt(st.nextToken());
		int c = Integer.parseInt(st.nextToken());

		int cap[] = new int[n + 1];
		st = new StringTokenizer(bf.readLine());
		for (int i = 1; i < n + 1; i++) {
			cap[i] = Integer.parseInt(st.nextToken());
		}

		Deque<Integer> back = new ArrayDeque<>();
		Deque<Integer> front = new ArrayDeque<>();

		int now = -1;
		int front_size = 0;
		int back_size = 0;

		for (int i = 0; i < q; i++) {
			st = new StringTokenizer(bf.readLine());
			char cmd = st.nextToken().charAt(0);

			if (cmd == 'B') {
				if (!back.isEmpty()) {
					front.add(now);
					front_size += cap[now];
					back_size -= cap[back.peekLast()];
					now = back.pollLast();
				}
			} else if (cmd == 'F') {
				if (!front.isEmpty()) {
					back.add(now);
					back_size += cap[now];
					front_size -= cap[front.peekLast()];
					now = front.pollLast();
				}
			} else if (cmd == 'A') {
				int num = Integer.parseInt(st.nextToken());
				front_size = 0;
				front.clear();

				if (now != -1) {
					back.add(now);
					back_size += cap[now];
				}

				now = num;

				while (front_size + back_size + cap[now] > c) {
					back_size -= cap[back.pollFirst()];
				}
			} else if (cmd == 'C') {
				Deque<Integer> temp = new ArrayDeque<>();
				for (int x : back) {
					if (temp.isEmpty()) {
						temp.add(x);
					} else {
						if (temp.peekLast() != x) {
							temp.add(x);
						} else {
							back_size -= cap[x];
						}
					}
				}
				back = temp;
			}
		}

		bw.write(now + "\n");

		if (back.isEmpty()) {
			bw.write(-1+"\n");
		} else {
			Iterator<Integer> iter1 = back.descendingIterator();
			while (iter1.hasNext()) {
				bw.write(iter1.next() + " ");
			}
			bw.write("\n");
		}


		if (front.isEmpty()) {
			bw.write(-1+"\n");
		} else {
			Iterator<Integer> iter2 = front.descendingIterator();
			while (iter2.hasNext()) {
				bw.write(iter2.next() + " ");
			}
		}
		bw.flush();
	}
}

 

Main

변수)
n : 웹페이지의 종류의 수
q : 작업의 개수
c : 최대 캐시 용량
cap : 각 웹페이지의 캐시 공간
back : Deque <Integer> 뒤로 가기 공간
front : Deque <Integer> 앞으로 가기 공간
now : 현재 페이지
front_size, back_size : 앞으로 가기 공간의 캐시 용량, 뒤로 가기 공간의 캐시 용량
cmd : 각 작업

 

- 웹 페이지의 종류의 수(n), 사용자가 수행하는 작업의 개수(q), 최대 캐시 용량(c) 입력

- 웹 페이지의 종류의 수(n)만큼 각 웹 페이지의 캐시 공간을 입력받아 cap 배열에 저장

- 작업의 개수(q)만큼 작업 입력받아 수행

: B라면 뒤로 가기 공간이 비어있는지 확인 후 비어있지 않다면 현재 페이지를 앞으로 가기 공간에 저장 후 앞으로 가기 공간의 캐시 용량 추가 및 뒤로 가기 공간에서 가장 최근의 페이지(pollLast)에 접속 

: F라면 앞으로 가기 공간이 비어있는지 확인 후 비어있지 않다면 현재 페이지를 뒤로 가기 공간에 저장 후 뒤로 가기 공간의 캐시 용량 추가 및 앞으로 가기 공간에서 가장 최근의 페이지(pollLast)에 접속

: A라면

1) 앞으로 가기 공간에 저장된 페이지가 모두 삭제되므로 clear 및 앞으로 가기 공간의 캐시 용량 0으로 저장

2) 처음으로 웹 페이지에 접속하는 경우가 아니라면(now!=-1) 현재 페이지를 뒤로 가기 공간에 추가

3) 처음으로 접속인지 상관없이 웹 페이지 접속

4) 사용 중인 캐시 용량 (앞으로 가기 공간 + 뒤로 가기 공간 + 현재 접속 중인 페이지)이 최대 캐시 용량(c)을 초과하는 경우 뒤로 가기 공간에서 가장 오래된 페이지 삭제(pollFirst)

: C라면 뒤로 가기 공간을 전체 탐색하며 같은 번호의 페이지가 연속해서 2개 이상 등장할 경우 하나만 남기고 제거

- 현재 접속 중인 페이지 번호 출력

- 뒤로 가기 공간이 비어있다면 -1 출력, 비어있지 않다면 가장 최근에 방문한 순서대로 출력하기 위해 뒤에서부터 탐색해서 출력

- 앞으로 가기 공간이 비어있다면 -1 출력, 비어있지 않다면 가장 최근에 방문한 순서대로 출력하기 위해 뒤에서부터 탐색해서 출력  

---

---