문제

이번 문제는 그냥 명확하게 스택을 구현하는 문제였다.
스택을 구현하려면 어떤 자료구조를 써야할지 고민하다가 LinkedList를 사용하기로 마음먹었다.

Stack이 뭔데?
LIFO(Last In, First Out) 구조를 가지며, 기본적인 연산에는 요소 추가(push), 제거(pop), 크기 확인(size), 비어있는지 확인(empty), 가장 위에 있는 요소 확인(top)이 있다.
문제에서 나오는 연산들이 있는 자료구조이다.

왜 LinkedList?

일단 동적으로 크기가 가변될 수 있다는 점에서 LinkedList를 사용했다. Stack도 쌓으면 쌓을 수록 크기가 늘어나기 때문에..!
그리고 addFirst()나 removeFirst()메서드를 사용하면 스택의 단방향 성격에 맞게 동작을 한다…
코드도 간단하게 작성할 수 있다. LinkedList의 내장메서드를 사용한다면 가독성이 매우 좋다.

일단 주어진 문제는 다음과 같다.

•	push X : 정수 X를 스택에 넣는다.
•	pop : 스택에서 가장 위에 있는 정수를 제거하고 출력한다. 비어 있으면 -1을 출력한다
•	size : 스택에 들어 있는 정수의 개수를 출력한다.
•	empty : 스택이 비어 있으면 1, 아니면 0을 출력한다.
•	top : 스택의 가장 위에 있는 정수를 출력한다. 비어 있으면 -1을 출력한다.

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

        for (int i = 0; i < n; i++) {
            String command = br.readLine();

            if (command.startsWith("push")) {
                int num = Integer.parseInt(command.split(" ")[1]);
                stack.addFirst(num); 
            } else if (command.equals("pop")) {
                if (stack.isEmpty()) {
                    bw.write("-1\n");
                } else {
                    bw.write(stack.removeFirst() + "\n");
                }
            } else if (command.equals("size")) {
                bw.write(stack.size() + "\n");
            } else if (command.equals("empty")) {
                bw.write((stack.isEmpty() ? "1" : "0") + "\n");
            } else if (command.equals("top")) {
                if (stack.isEmpty()) {
                    bw.write("-1\n");
                } else {
                    bw.write(stack.getFirst() + "\n");
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

다시 곰곰히 생각해보니 배열로.. 만들어보는게 이 문제의 의도였을 것 같아서 배열로 코드를 다시 짜보았다.
LinkedList로 구현할거면 차라리 Stack으로 바로처리했지.. ;< 나 바본가..?

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[] stack = new int[10000]; // 최대 크기 10,000으로 설정!!
        int top = -1; // 스택의 초기 위치

        for (int i = 0; i < n; i++) {
            String command = br.readLine();

            if (command.startsWith("push")) {
                int num = Integer.parseInt(command.split(" ")[1]);
                stack[++top] = num; 
            } else if (command.equals("pop")) {
                if (top == -1) {
                    bw.write("-1\n"); 
                } else {
                    bw.write(stack[top--] + "\n")
                }
            } else if (command.equals("size")) {
                bw.write((top + 1) + "\n"); 
            } else if (command.equals("empty")) {
                bw.write((top == -1 ? "1" : "0") + "\n"); 
            } else if (command.equals("top")) {
                if (top == -1) {
                    bw.write("-1\n");
                } else {
                    bw.write(stack[top] + "\n"); 
                }
            }
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

배열을 그냥 사이즈만 최대로 시켜놓고 스택을 구현하는 게 문제의 의도 아니였을까?

일단 연산이 빠르다. 모든 연산이 전부 시간복잡도 O(1)을 가진다.