[백준] 23294 웹 브라우저 1 - Java

 

 

 

문제 출저

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

23294번: 웹 브라우저 1

 

 

 

문제 풀이

구현 문제입니다. 

4가지 기능(뒤로 가기, 앞으로 가기, 웹 페이지 접속, 압축)을 Deque를 이용하여 구현했습니다. 

 

 

 

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

/*
웹 브라우저1
https://www.acmicpc.net/problem/23294

뒤로 가기 공간
앞으로 가기 공간
캐시 변수

각 기능 구현

1% 오답
앞으로 가기 로직 수정

3% 출력 형식이 잘 못 되었습니다.
println 형식 수정
 */

public class Main {

    static int n, q, c; // 웹 페이지 종류, 작업의 개수, 최대 캐시 용량
    static int[] caps; // 웹 페이지 별 캐시 공간 크기
    static Deque<Integer> frontSpace; // 앞으로 가기 공간
    static Deque<Integer> backSpace; // 뒤로 가기 공간
    static int nowPage; // 현재 페이지
    static int nowCap; // 현재 저장 공간 용량


    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        q = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());

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

        frontSpace = new LinkedList<>();
        backSpace = new LinkedList<>();

        while(q-->0) {
            String[] spt = br.readLine().split(" ");

            // 뒤로 가기 실행
            if (spt[0].equals("B")) {
                moveBack();
            }

            // 앞으로 가기 실행
            if (spt[0].equals("F")) {
                moveFront();
            }

            //  웹 페이지 접속
            if (spt[0].equals("A")) {
                int number = Integer.parseInt(spt[1]);
                moveWebPage(number);
            }

            // 압축 실행
            if (spt[0].equals("C")) {
                compact();
            }

//            System.out.println(spt[0]);
//            System.out.println(nowPage);
//            System.out.println(nowCap);
//            System.out.println(backSpace);
//            System.out.println(frontSpace);
//            System.out.println();

        }

        System.out.println(nowPage);

        if (backSpace.isEmpty()) System.out.print(-1);
        else {
            while (!backSpace.isEmpty()) {
                System.out.print(backSpace.pollLast() + " ");
            }
        }

        System.out.println();

        if (frontSpace.isEmpty()) System.out.print(-1);
        else {
            while (!frontSpace.isEmpty()) {
                System.out.print(frontSpace.pollLast() + " ");
            }
        }


    }



    // 뒤로 가기 실행
    private static void moveBack() {
        // 뒤로 가기 공간이 0일 때 무시
        if (backSpace.isEmpty()) return;

        // 현재 보고 있던 웹 페이지를 앞으로 가기 공간에 저장
        frontSpace.add(nowPage);

        // 뒤로 가기 공간에 방문한 가장 최근 페이지에 접속
        nowPage = backSpace.pollLast();

    }

    // 앞으로 가기 실행
    private static void moveFront() {

        if (frontSpace.isEmpty()) return;

        // 현재 보고 있던 페이지를 뒤로 가기 공간에 저장
        backSpace.add(nowPage);

        // 앞으로 가기 공간에 방문한지 가장 최근 페이지에 접속
        nowPage = frontSpace.pollLast();
    }

    // 웹 페이지 접속
    private static void moveWebPage(int number) {

        // 앞으로 가기 공간에 저장된 페이지 모두 삭제
        while(!frontSpace.isEmpty()) {
            nowCap -= caps[frontSpace.pollFirst()];
        }

        // 현재 페이지를 뒤로 가기에 저장
        if (nowPage != 0) {
            backSpace.add(nowPage);
        }

        // 접속할 페이지 현재 페이지로 개신, 용량만큼 캐시 용량 추가
        nowPage = number;
        nowCap += caps[number];

        while(nowCap > c) {
            nowCap -= caps[backSpace.pollFirst()];
        }

    }

    // 압축
    private static void compact() {
        Deque<Integer> temp = new LinkedList<>();

        while (!backSpace.isEmpty()) {
            int number = backSpace.pollFirst();
            if (!temp.isEmpty() && temp.getLast() == number) {
                nowCap -= caps[number];
            }
            else {
                temp.add(number);
            }
        }

        backSpace = new LinkedList<>();
        while (!temp.isEmpty()) {
            backSpace.add(temp.pollFirst());
        }

    }



}