[백준] 10828번 스택 - 자바 문제 풀이 (Stack, List)

 

문제

정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 다섯 가지이다.

• push X: 정수 X를 스택에 넣는 연산이다.
• pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 스택에 들어있는 정수의 개수를 출력한다.
• empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
• top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.

 

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다

 

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

---

 

 

먼저 이 문제를 이해하기 위해서는 자료구조 [스택]에 대해 알아야 한다. 스택에 대한 내용은 다음 글에서 확인할 수 있다.
[자료구조] 스택(Stack) & 큐(Queue), 그리고 데크(Deque)

[자료구조] 스택(Stack) & 큐(Queue), 그리고 데크(Deque)

 

처음엔 자바에서 제공하는 Stack을 사용해서 아래와 같이 풀어보았다.

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 {
        Stack<Integer> stack = new Stack<>();

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        Integer N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {

            st = new StringTokenizer(br.readLine());
            String opr = st.nextToken();

            if(opr.equals("push")) {
                Integer num = Integer.parseInt(st.nextToken());
                stack.push(num);
            }

            else if (opr.equals("pop")) {
                if(stack.empty())
                    System.out.println(-1);
                else
                    System.out.println(stack.pop());
            }

            else if (opr.equals("top"))
                if(stack.empty())
                    System.out.println(-1);
                else
                    System.out.println(stack.peek());

            else if (opr.equals("size"))
                System.out.println(stack.size());

            else if (opr.equals("empty")){
                if (stack.empty())
                    System.out.println(1);
                else
                    System.out.println(0);
            }
        }
    }
}

 

# 1.

import java.util.Stack;
...
Stack<Integer> stack = new Stack<>();

정수형의 데이터를 받을 스택을 생성하였다. 자바에서 제공하는 프레임워크로 import java.util.Stack을 추가해야 한다.
스택의 기본 연산인 push, pop, peek이 모두 구현되어 있다.

 

# 2.
equals로 입력받은 문자를 비교해 각 연산을 진행한다.
- push, pop, top은 각각 Stack.push(Element), Stack.pop(), Stack.peek()을 이용하였다.
- size는 Stack에서 제공하는 메서드인 Stack.size()로 스택에 들어간 데이터의 수를 가져왔다.
- empty는 Stack.empty로 스택이 비어있으면 true를 반환한다. 스택이 비어있는지 확인하는 모든 부분에 이 메서드를 사용해주었다. (pop과 top)

 

---

 

Stack을 이용해 풀다가 그냥 리스트를 이용해 풀 수 있을 것 같아 List로 변경해보았다.

2. List 사용

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

		// BufferedReader, StringTokenizer, Integer N 동일

        List<Integer> stack = new ArrayList<>();

        for (int i = 0; i < N; i++) {
			
            // 위와 동일

            if(opr.equals("push")) {
                Integer num = Integer.parseInt(st.nextToken());
                stack.add(num);
                // Stack.push → List.add
            }

            else if (opr.equals("pop")) {
                if(stack.isEmpty())
                    System.out.println(-1);
                else
                    System.out.println(stack.remove(stack.size() - 1));
                    // Stack.pop → List.remove
            }

            else if (opr.equals("top"))
                if(stack.isEmpty())
                    System.out.println(-1);
                else
                    System.out.println(stack.get(stack.size()-1));
                    // Stack.peek → List.get

            else if (opr.equals("size"))
                System.out.println(stack.size());

            else if (opr.equals("empty")){
                if (stack.isEmpty())
                    System.out.println(1);
                else
                    System.out.println(0);
            }
        }
    }

변경한 부분만 설명하면 아래와 같다.

 

# 1.
Stack에서 데이터 삽입을 의미하는 push연산은 리스트의 add메서드를 이용할 수 있다.

 

#2.
Stack에서는 쉽게 제일 마지막 데이터를 가져올 수 있다.
하지만 List에서는 마지막 인덱스에 접근하여 데이터를 가져와야 한다.

마지막 인덱스에 접근하기 위해 List.size()를 이용하였다. size메서드는 리스트에 들어간 데이터의 수를 가져오는데, 각 리스트는 인덱스 0번부터 시작하기 때문에 데이터 하나를 삽입하면 size=1, index=0이 된다.
List.size()-1 로 크기를 하나 줄이면 해당 인덱스를 구할 수 있다.

 

#3.
2번의 방법으로 pop과 peek(문제에서 top)을 구현하였다. 
pop은 해당 인덱스의 데이터를 삭제하기 위해 remove메서드를 이용하였고,
peek은 마지막 인덱스의 데이터를 반환시키는 것으로 get메서드를 사용하였다.