[백준(Java)] 10828. 스택 (배열 VS ArrayList)

문제

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

명령은 총 다섯 가지이다.

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

입력

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

출력

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

 

예제 입력

14
push 1
push 2
top
size
empty
pop
pop
pop
size
empty
pop
push 3
empty
top

 

예제 출력

2
2
0
2
1
-1
0
1
-1
0
3

 

내 풀이:

 

sc.nextLine()을 통해 입력받은 명령어 command에 따라서 스택을 구현하는 프로그램이다. 처음, 이 문제를 보았을 떄, ArrayList<Integer>를 이용하여 내부적으로 자동으로 크기를 조절하여 코드를 작성하였다. 하지만, Integer 객체를 사용하기 때문에 메모리 사용량과 속도가 느려서, 문제에서 요구하는 조건을 맞추지 못하고 "시간 초과" 의 결과가 나왔다.

(Integer 객체에 스택의 계산을 위해서는 int 타입을 변환하는 UnBoxing 과정이 필요하기 때문에, 속도 저하)

 

-> 이 문제를 해결하기 위해, ArrayList<Integer> 대신에 Int<> 배열을 사용하였다. 이 방법은, 전체 배열의 크기가 고정되어 있다는 문제가 있긴 하지만, 해당 문제에서의 전체 입력의 수를 배열의 크기로 설정하여, 오버플로우 문제를 방지할 수 있다.

# ArrayList 버전

import java.util.ArrayList;
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine(); // 개행 문자 제거

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

        for (int i = 0; i < N; i++) {
            String command = sc.nextLine();

            if (command.startsWith("push")) {
                int value = Integer.parseInt(command.split(" ")[1]);
                stack.add(value);
            } else if (command.equals("pop")) {
                if (stack.isEmpty()) {
                    System.out.println(-1);
                } else {
                    System.out.println(stack.remove(stack.size() - 1));
                }
            } else if (command.equals("size")) {
                System.out.println(stack.size());
            } else if (command.equals("empty")) {
                System.out.println(stack.isEmpty() ? 1 : 0);
            } else if (command.equals("top")) {
                if (stack.isEmpty()) {
                    System.out.println(-1);
                } else {
                    System.out.println(stack.get(stack.size() - 1));
                }
            }
        }

        sc.close();
    }
}

 

# Int[] 버전

import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        sc.nextLine(); // 개행 문자 제거

        int[] stack = new int[N];
        int top = -1;

        for (int i = 0; i < N; i++) {
            String command = sc.nextLine();

            if (command.startsWith("push")) {
                int value = Integer.parseInt(command.split(" ")[1]);
                stack[++top] = value;
            } else if (command.equals("pop")) {
                if (top == -1) {
                    System.out.println(-1);
                } else {
                    System.out.println(stack[top--]);
                }
            } else if (command.equals("size")) {
                System.out.println(top + 1);
            } else if (command.equals("empty")) {
                System.out.println(top == -1 ? 1 : 0);
            } else if (command.equals("top")) {
                if (top == -1) {
                    System.out.println(-1);
                } else {
                    System.out.println(stack[top]);
                }
            }
        }

        sc.close();
    }
}

 

Int [N] 배열 사용으로 인해 문제에서 요구하는 조건에 모두 충족하였다.

결론 및 정리:

1. 메모리 측면

1) 배열 (int[])

• 정적 배열: 크기가 고정되며, int 타입은 4바이트를 차지합니다.
• 예를 들어, int[10000]이면 약 40KB의 메모리만 사용됩니다.
• **원시 타입(primitive type)**이므로, 추가적인 객체 오버헤드 없음.

2) ArrayList<Integer>

• 내부적으로는 Object[] 배열을 사용하여 자동으로 크기 조절.
• int는 사용할 수 없고, 반드시 Integer 객체로 Boxing되어 들어감.
• Integer는 객체이므로,
  • int 값(4B) + 객체 오버헤드(12~16B) → 한 요소당 약 16~20B 이상 차지.
  • 추가적으로 내부 배열의 빈 공간도 존재.
• 10000개 원소 저장 시 메모리는 약 160KB 이상.

정리: 메모리는 배열(int[])이 훨씬 적게 사용됨.
ArrayList<Integer>는 boxing과 객체 오버헤드 때문에 4배 이상 메모리 사용.

---

2. 속도 측면

1) 배열 (int[])

• 원시 타입이므로 Boxing/Unboxing이 없음.
• 인덱스 기반 접근 속도 빠름: O(1)
• push, pop, top 모두 상수 시간에 처리 가능.

2) ArrayList<Integer>

• add()나 remove()는 평균적으로 O(1)이지만,
  • 내부 배열이 가득 찼을 경우, resize(복사) 발생 → O(n)
• Integer 사용으로 Boxing/Unboxing 비용 발생.
• remove()나 get()은 인덱스 접근이므로 속도는 빠르지만, primitive 배열보다 느림.

정리: int[] 배열이 속도 면에서도 우위. 특히 반복문 내에서 성능 차이가 커질 수 있음

---

 

• 시간과 메모리가 중요한 문제 (예: 백준, 알고리즘 대회 등):
  → ✅ int[] 사용 추천
• 확장성과 편의성이 중요한 일반 애플리케이션:→ ✅ ArrayList<Integer> 사용 고려

깃허브 주소:

https://github.com/Chaehyunli/BaekJoon/tree/main/%EB%B0%B1%EC%A4%80/Silver/10828.%E2%80%85%EC%8A%A4%ED%83%9D

BaekJoon/백준/Silver/10828. 스택 at main · Chaehyunli/BaekJoon