[BOJ] 23294번: 웹 브라우저 1 Java 풀이

🚩 Introduction
스터디 중 코테에 가끔 등장하는 유형인 웹 브라우저 탐색 문제를 풀게 되었다. 구글링을 해도 답이 많지 않고, 푼 사람도 적은 문제라 도움이 될까 싶어 올린다.

📌 문제

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

23294번: 웹 브라우저 1

📝 설명

간단히 뒤로 가기와 앞으로 가기에 있는 페이지 번호들을 각각 Deque 과 Stack 에 넣어서 풀었다. volume 이라는 변수로 현재 사용되는 캐시 용량을 계속 추적하고, 이 값이 max (문제에서는 C) 를 넘어서면 Deque 의 removeFirst 메서드를 이용해 가장 예전에 방문한 페이지를 제거해준다. 페이지를 방문할 때마다 Stack 은 clear() 메서드를 사용해 비워주고, 비워진 만큼 용량을 계산해 volume 에서 빼 주었다.

 

1. 처음에 입력을 받을 때 무심코 toCharArray() 를 사용했는데, A i (페이지 접근 명령) 을 저장한 char 배열에서 2번째를 접근하니까 공백 문자가 나와 문제가 풀리지 않았다. 이후에 StringTokenizer 를 사용하여 올바르게 입력을 받도록 변경해주어 문제를 해결할 수 있었다.
2. Stack 과 Deque 자료구조는 인덱스를 가지고 원소에 접근할 수 없다. 그래서 모두 ArrayList 형태로 바꿔준 뒤에 인덱스를 참조하여 원소를 가져오도록 해야 했다. 출력을 할 때도 마찬가지로 ArrayList로 변환한 뒤에 맨 뒤의 원소부터 (가장 최근에 방문한 순) 출력하도록 했다.

💡 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

  static Deque<Integer> past;
  static Stack<Integer> rollback;
  static int volume = 0;
  static int current = -1;
  static int[] sizes;
  static int max;

  public static void goBackward() {
    if (past.isEmpty()) {
      return;
    }

    rollback.push(current);
    current = past.removeLast();
  }

  public static void goFrontward() {
    if (rollback.isEmpty()) {
      return;
    }

    past.addLast(current);

    current = rollback.pop();
  }

  public static void access(int target) {
    if (current != -1) {
      past.addLast(current);
    }

    if (!rollback.isEmpty()) {
      int total = 0;
      for (int r : rollback) {
        total += sizes[r];
      }
      volume -= total;
      rollback.clear();
    }

    current = target;
    volume += sizes[target];

    if (volume > max) {
      while (volume > max && !past.isEmpty()) {
        volume -= sizes[past.getFirst()];
        past.removeFirst();
      }
    }

  }

  public static void compress() {
    int cur = -1;
    List<Integer> p = new ArrayList<>(past);
    for (int i = 0; i < p.size(); i++) {
      if (cur != -1 && cur == p.get(i)) {
        while (i < p.size() && p.get(i) >= 0 && cur == p.get(i)) {
          volume -= sizes[p.get(i)];
          p.set(i, -1);
          i++;
        }
//        p.set(i-1, cur);
      }
      if (i < p.size()) {
        cur = p.get(i);
      }
    }
    int n = 0;
    while (p.contains(-1)) {
      if (p.get(n) == -1) {
        p.remove(n);
        continue;
      }
      n++;
    }
    past = new LinkedList<>(p);
  }

  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    StringTokenizer st = new StringTokenizer(br.readLine(), " ");
    int N = Integer.valueOf(st.nextToken());
    int Q = Integer.valueOf(st.nextToken());
    max = Integer.valueOf(st.nextToken());

    sizes = new int[N + 1];

    st = new StringTokenizer(br.readLine(), " ");

    for (int i = 1; i <= N; i++) {
      sizes[i] = Integer.valueOf(st.nextToken());
    }

    past = new LinkedList<>();
    rollback = new Stack<>();

    for (int i = 0; i < Q; i++) {
      st = new StringTokenizer(br.readLine(), " ");
      String command1 = st.nextToken();
      String command2 = "";
      if (st.hasMoreTokens()) {
        command2 = st.nextToken();
      }

      if (command1.equals("B")) {
        goBackward();
      }

      if (command1.equals("F")) {
        goFrontward();
      }

      if (command1.equals("A")) {
        access(Integer.valueOf(command2));
      }

      if (command1.equals("C")) {
        compress();
      }
    }

    System.out.println(current);

    StringBuilder sb1 = new StringBuilder();
    if (past.isEmpty()) {
      System.out.println(-1);
    } else {
      List<Integer> p = new ArrayList<>(past);
      for (int i = p.size() - 1; i >= 0; i--) {
        if (i == 0) {
          sb1.append(p.get(i));
        } else {
          sb1.append(p.get(i) + " ");
        }
      }
      System.out.println(sb1);
    }

    StringBuilder sb2 = new StringBuilder();
    if (rollback.isEmpty()) {
      System.out.print(-1);
    } else {
      List<Integer> r = new ArrayList<>(rollback);
      for (int i = r.size()-1; i >= 0; i--) {
        if (i == 0) {
          sb2.append(r.get(i));
        } else {
          sb2.append(r.get(i) + " ");
        }
      }
      System.out.print(sb2);
    }

  }

}