[백준] 10828번: 스택

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

 

💡문제 분석 요약

스택을 구현하여 “연산 숫자”로 이루어진 명령에 따라 스택을 조작하는 문제이다.

💡알고리즘 설계

Scanner 클래스를 이용하여 N(명령의 수)과 명령을 입력받았다.

Stack 클래스를 이용하여 주어지는 명령에 해당하는 메서드를 이용했다.

• push x: push 메서드 이용하여 값 출력
• pop
  • isEmpty 메서드를 이용해 스택이 비어있는지 확인
  • pop 메서드 이용하여 값 출력
• size: size 메서드 이용하여 값 출력
• empty: isEmpty 메서드를 이용해 스택이 비어있는지 확인
• top
  • isEmpty 메서드를 이용해 스택이 비어있는지 확인
  • peek 메서드 이용하여 값 출력

💡코드

import java.util.Scanner;
import java.util.Stack;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Stack<Integer> stack = new Stack<>();

        while(n>0){
            String s = sc.next();

            if(s.equals("push")){
                int num = sc.nextInt();
                stack.push(num);
            } else if(s.equals("pop")){
                if(stack.isEmpty()) System.out.println(-1);
                else System.out.println(stack.pop());
            } else if(s.equals("size")){
                System.out.println(stack.size());
            } else if(s.equals("empty")){
                if(stack.isEmpty()) System.out.println(1);
                else System.out.println(0);
            } else {
                if(stack.isEmpty()) System.out.println(-1);
                else System.out.println(stack.peek());
            }

            n--;
        }
    }
}

💡시간복잡도

코드의 전체 시간복잡도는 O(n)이고, 각 연산의 시간복잡도는 O(1)이다.

💡 틀린 이유

시간초과

Scanner의 속도가 느림.

💡 틀린 부분 수정 or 다른 풀이

BufferedReader를 사용하여 입력을 한 줄씩 읽어들이고, StringTokenizer를 사용하여 각 줄을 공백을 기준으로 분리하여 처리했다.

모든 출력 결과를 StringBuilder에 저장하고 마지막에 한 번에 출력하도록 했다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class Main {

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

        int n = Integer.parseInt(br.readLine());
        Stack<Integer> stack = new Stack<>();

        while(n>0){
            st = new StringTokenizer(br.readLine(), " ");
            String op = st.nextToken();

            if(op.equals("push")){
                int num = Integer.parseInt(st.nextToken());
                stack.push(num);
            } else if(op.equals("pop")){
                if(stack.isEmpty()) sb.append("-1\\n");
                else sb.append(stack.pop()).append("\\n");
            } else if(op.equals("size")){
                sb.append(stack.size()).append("\\n");
            } else if(op.equals("empty")){
                if(stack.isEmpty()) sb.append("1\\n");
                else sb.append("0\\n");
            } else {
                if(stack.isEmpty()) sb.append("-1\\n");
                else sb.append(stack.peek()).append("\\n");
            }
            n--;
        }
        System.out.println(sb.toString());
        br.close();
    }
}

💡 느낀점 or 기억할정보

• 보통 Scanner를 이용해서 입력 받았는데, Scanner가 속도가 느리다는 사실을 이번 과제를 통해 알게 되었다. 입출력은 Scanner 보다 BufferedReader를 사용하는 것이 더 빠르다.
• 백준에서 자바 코드를 제출할 때는 확인해야 하는 것들이 존재한다.
  • 클래스 이름은 Main으로 설정.
  • 패키지 이름 제거