99클럽 코테 스터디 11일차 TIL + 스택

오늘의 학습 키워드 및 문제

#스택 #Stack #ArrayDeque
백준 실버4) 스택

문제풀이

문제에서 거의 다 알려주었다.
Stack에 대하여 알고있다면 어렵지 않은 문제이다.

1. 명령의 수 n 입력받음
2. 입력받은 명령어를 switch로 처리
   2-1. StringTokenizer를 사용하여 첫번째 입력 문자열을 switch문과 비교
   2-2. push, pop, size, ... 에 알맞게 처리

❗java.util.EmptyStackException

첫번째 시도 후 해당 에러가 발생했다.
찾아보니 pop과 top을 처리할 때는 항상 stack의 내용이 비어있는지 확인해야 된다고 한다.
(나는 top을 처리할 때 empty 여부를 안했음..)
수정하고 다시 제출하니 정상적으로 실행되었다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();
        
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            switch(st.nextToken()) {
                case "push":
                    stack.push(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    System.out.println(stack.empty() ? -1 : stack.pop());
                    break;
                case "size":
                    System.out.println(stack.size());
                    break;
                case "empty":
                    System.out.println(stack.empty() ? 1 : 0);
                    break;
                case "top":
                    System.out.println(stack.empty() ? -1 : stack.peek());
                    break;
                default:
                    break;
            }
        }
        br.close();
    }
}

다른방법

1. Stack 대신 ArrayDeque 사용

ArrayDeque는 Stack이기도 하고 Queue이기도 하다.
ArrayDeque가 더 빠르다고 했지만 해당 문제에서 큰 차이를 보이진 못함.
[기존방법] 18876KB 288ms
[다른방법] 19356KB 284ms

• Stack

  • 동기화됨 (Thread-Safe)
  • Vector<E> 상속받음 (동기화도 해당 클래스 덕분)
  • 상대적으로 느림 (동기화 때문)
  • Stack 전용 (LIFO)

• ArrayDeque

  • 동기화되지 않음 (Not Thread-Safe)
  • AbstractCollection<E> 상속받음
  • 더 빠름 (비동기)
  • Stack + Queue (LIFO & FIFO)

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            switch(st.nextToken()) {
                case "push":
                    stack.push(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    System.out.println(stack.isEmpty() ? -1 : stack.pop());
                    break;
                case "size":
                    System.out.println(stack.size());
                    break;
                case "empty":
                    System.out.println(stack.isEmpty() ? 1 : 0);
                    break;
                case "top":
                    System.out.println(stack.isEmpty() ? -1 : stack.peek());
                    break;
                default:
                    break;
            }
        }
        br.close();
    }
}

2. 출력 방식에 따라 속도가 이렇게나?

다른 사람들과 메모리, 시간을 비교했더니 시간이 나보다 훨씬 빠른 사람들이 있었다.
코드를 확인해보니 출력하는 방식에 차이가 있었다.
나는 StringBuilder로 바꿔서 다시 해보니 속도가 빨라진 것을 확인할 수 있었다.
[기존방법] 18876KB 288ms
[다른방법] 18820KB 152ms

참고) 백준 - 출력 속도 비교

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int n = Integer.parseInt(br.readLine());
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        StringBuilder sb = new StringBuilder();
        
        for(int i=0; i<n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            switch(st.nextToken()) {
                case "push":
                    stack.push(Integer.parseInt(st.nextToken()));
                    break;
                case "pop":
                    sb.append(stack.isEmpty() ? -1 : stack.pop()).append('\n');
                    break;
                case "size":
                    sb.append(stack.size()).append('\n');
                    break;
                case "empty":
                    sb.append(stack.isEmpty() ? 1 : 0).append('\n');
                    break;
                case "top":
                    sb.append(stack.isEmpty() ? -1 : stack.peek()).append('\n');
                    break;
                default:
                    break;
            }
        }
        System.out.println(sb);
        br.close();
    }
}

공부한 내용정리

• Stack에서 pop과 peek를 사용할 때는 항상 데이터가 없는지 확인해야 한다. 확인하지 않으면 java.util.EmptyStackException 발생
• Stack과 비슷한 ArrayDeque클래스가 있다. 이 클래스는 스레드에 안전하지 않지만 Stack보다 더 빠르고 Stack처럼 사용 할 수도 Queue처럼 사용 할 수도 있다.