백준 23294번

문제 23294(실패, 어떠한 예외 상황에 대해서 처리하지 못한 것으로 판단 됨.)

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

소스코드

import java.io.*;
import java.util.*;
public class boj23294 {
    static int Max = 2001;
    static int[] cashValue = new int[Max];      // N의 한계치 == 2000
    static int C;           //한도 캐쉬 값
    static StringBuilder sb = new StringBuilder();
    static Stack<Integer> stack1 = new Stack<>();       //현재위치
    static Stack<Integer> stack2= new Stack<>();        //앞 저장소
    static Deque<Integer> stack3= new ArrayDeque<>();       //뒤 저장소
    static int curcash = 0;     //현재 주소 캐쉬 값
    static int frontcash = 0;       //앞 저장소 캐쉬 값
    static int backcash = 0;        // 뒷 저장소 캐쉬 값
    static int cashsum = 0;         //캐쉬 총 합
    static boolean isTrue = true;       //메모리 초과를 해결할 수 없는 상황 예외처리
    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.parseInt(st.nextToken());   //종류 N
        int Q = Integer.parseInt(st.nextToken());   //수행 횟수 Q
        C = Integer.parseInt(st.nextToken());       //한계 C
        st = new StringTokenizer(br.readLine());
        //cash 값을 주소에 맞게 배열로 저장
        for (int i = 1; i <= N; i++) {
            cashValue[i] = Integer.parseInt(st.nextToken());
        }
        int cnt = 0;
        while(cnt < Q){     //Q번 만큼 작업 실행
            String input = br.readLine();
            web(input);     //작업 함수 web
            cnt++;
        }
        if(isTrue && !stack1.isEmpty()) {   //예외처리가 완성되고, 현재 웹이 켜져있는 경우
            sb.append(stack1.peek() + "\n");
            if (stack3.isEmpty()) {
                sb.append(-1 + "\n");
            } else {
                while (!stack3.isEmpty()) {
                    sb.append(stack3.pollLast() + " ");
                }
                sb.append("\n");
            }
            if (stack2.isEmpty()) {
                sb.append(-1 + "\n");
            } else {
                while (!stack2.isEmpty()) {
                    sb.append(stack2.pop() + " ");
                }
            }
            System.out.println(sb);
        }
    }
    public static void web(String input){
        char[] arr = input.toCharArray();
        int num =0;
        if(arr.length != 1){
            num = arr[2] - 48;
        }
        switch(arr[0]- 'A'){
            case 0:     //num번 페이지에 접속
                stack2.clear();
                frontcash =0;
                if(stack1.isEmpty()){
                    stack1.add(num);
                    curcash += cashValue[num];
                }else {
                    int key = stack1.pop();
                    stack3.add(key);
                    stack1.add(num);
                    curcash += cashValue[num] - cashValue[key];
                    backcash += cashValue[key];
                    cashsum = backcash + curcash + frontcash;
                    while(cashsum > C && !stack3.isEmpty()){
                        int a = stack3.pollFirst();
                        backcash -= cashValue[a];
                        cashsum = backcash + curcash + frontcash;
                    }
                    if(cashsum > C){
                        isTrue = false;
                    }
                }
                break;
            case 1:     //뒤로가기 실행
                if (!stack3.isEmpty()) {
                    int a = stack1.pop();
                    stack2.add(a);
                    int b = stack3.pollLast();
                    stack1.add(b);
                    curcash += cashValue[b] - cashValue[a];
                    frontcash += cashValue[a];
                    backcash -= cashValue[b];
                    cashsum = backcash + curcash + frontcash;
                }
                break;
            case 2:     //압축 실행
                if(!stack3.isEmpty()) {
                    HashSet<Integer> hs = new HashSet<>();
                    int size = stack3.size();
                    for (int i = 0; i < size; i++) {
                        if (!hs.contains(stack3.peekLast())) {
                            hs.add(stack3.peekLast());
                            stack3.addFirst(stack3.pollLast());
                        } else {
                            backcash -= stack3.pollLast();
                        }
                    }
                    cashsum = backcash + curcash + frontcash;
                }
                break;
            case 5:     //앞으로 가기 실행
                if (!stack2.isEmpty()) {
                    int a = stack1.pop();
                    stack3.add(a);
                    int b = stack2.pop();
                    stack1.add(b);
                    curcash += cashValue[b] - cashValue[a];
                    frontcash -= cashValue[b];
                    backcash += cashValue[a];
                    cashsum = backcash + curcash + frontcash;
                }
                break;
        }
    }
}

풀이 접근

1. 문제에서 현재, 뒤, 앞 주소들에 접근할 때 가장 최근에 방문 했던 주소를 가지고 이용함으로 Stack 자료구조를 사용하였다.
2. 접속(A)부분에서 캐쉬 초과시 뒤 주소들 중 가장 뒤에 있는 값의 제거가 필요하기 때문에 뒤 주소에는 Deque 자료구조를 사용하였다.
   -- Stack : stack1 = 현재, stack2 = 앞 주소 && Deque stack3 = 뒤 주소 --
3. 사용할 수 있는 주소의 종류가 최대 2000이기 때문에 전역변수로 cashValue 배열은 2001개의 배열로 잡는다.
4. 현재, 뒤, 앞, 전체 cashValue 값을 보여주는 변수들은 전역변수로, 예외처리를 위한 boolean isTrue도 전역변수로 만든다.
5. switch~ case를 이용하여 A,B,F,C를 문제에서 주어진 조건에 따라 만들고, 조건에 맞추어 case를 break 하기 전에 cashsum 값을 업데이트해 준다.
6. A가 들어가는 case에서 cashsum 값이 C보다 높은데 stack3에서 지울 내용물이 없다면 isTrue를 false로 만들어준다.
7. isTrue가 true이고, 현재 웹페이지가 열려있을 때(!stack1.isEmpty()) 출력한다.

문제 핵심

• 자료구조를 이해해서 활용할 수 있는지.
• 예외 상황에 대해 처리가 잘 되어 있는지.
• 케이스에 맞게 cashvalue들을 잘 사용 했는지.