[Baekjoon] 10828 - 스택

📝 문제

 

 

🔑 풀이 과정

사실 이 문제는, 문제에 어떻게 구현을 해야하는지가 다 나와있고

그걸 코드로만 짜면 되는 문제! 스택개념을 몰라도 문제 그대로 풀면 맞을 수 있는 문제.

① 일반적인 배열을 활용한 문제 풀이

명령의 개수가 N개이므로, 크기가 N인 int형 배열 선언(N개의 명령이 전부 push일 경우 최대 크기)

 

index를 선언해 준다.

여기서 index는 "다음에 데이터가 들어갈 위치"이다.

만약 데이터가 2개 차있으면(stack[0], stack[1]) index는 2가 되는 것.

index는 배열에 들어있는 데이터의 개수를 의미하기도 한다.

또한 스택이 비어있는지 여부를 index가 0인지 아닌지로 확인할 것.

 

나머지부분은 문제 조건에 맞게 작성해 준다.

② Stack 클래스를 활용한 문제 풀이

- 앞 풀이에서 index로 스택이 비어있는지 확인하는 부분을 Stack의 empty() 메서드로 바꿔준다.

그리고 각 조건에 맞게 Stack 클래스의 메서드를 활용해주면 된다.

Stack 클래스에 대한 글은 여기

https://seohyun0916.tistory.com/69

[JAVA] 자바 Stack(스택) 클래스

 

+ 이 문제는 시간 제한 0.5초이고, 언어별 추가시간이 없다.

그러므로 시간을 단축시키는 것도 중요.

명령의 개수가 10,000개, 단일 for문 알고리즘이라 알고리즘보다 입출력에서 시간을 단축시키는 것이 중요.

실제로 채점해 봤을 때

BufferedReader + System.out.println() 의 경우: 376ms

BufferedReader + BufferedWriter의 경우: 212ms

 

 

 

🔓 답안

① 일반적인 배열을 활용한 답안(BufferedReader + System.out.println())

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

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[] stack = new int[N];
        int index = 0;

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();

            if(str.equals("push")){
                int item = Integer.parseInt(st.nextToken());
                stack[index] = item;
                index++;
            } else if(str.equals("pop")){
                if(index == 0)
                    System.out.println(-1);
                else{
                    System.out.println(stack[index-1]);
                    index = index - 1;
                }
            } else if(str.equals("size")){
                System.out.println(index);
            } else if(str.equals("empty")){
                if(index == 0)
                    System.out.println(1);
                else
                    System.out.println(0);
            } else if(str.equals("top")){
                if(index == 0)
                    System.out.println(-1);
                else
                    System.out.println(stack[index-1]);
            }
        }


    }

}

② Stack 클래스를 활용한 답안

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));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());

        Stack<Integer> stack = new Stack<>();

        for(int i = 0; i < N; i++){
            st = new StringTokenizer(br.readLine());
            String str = st.nextToken();

            if(str.equals("push")){
                int item = Integer.parseInt(st.nextToken());
                stack.push(item);
            } else if(str.equals("pop")){
                if(stack.empty())
                    System.out.println(-1);
                else
                    System.out.println(stack.pop());
            } else if(str.equals("size")){
                System.out.println(stack.size());
            } else if(str.equals("empty")){
                if(stack.empty())
                    System.out.println(1);
                else
                    System.out.println(0);
            } else if(str.equals("top")){
                if(stack.empty())
                    System.out.println(-1);
                else
                    System.out.println(stack.peek());
            }
        }
    }

}