[java] 스택(Stack) 완벽 구현: 배열 덮어쓰기 vs Stack 클래스

알고리즘 문제를 풀다 보면 "가장 마지막에 넣은 데이터를 먼저 빼야 하는" 상황이 자주 발생합니다. (예: 괄호 짝 맞추기, 뒤로 가기 버튼, 최근 숫자 지우기 등)

이럴 때 사용하는 자료구조가 바로 스택(Stack), 즉 LIFO(Last In, First Out) 구조입니다. 오늘은 자바에서 스택 로직을 구현할 때 흔히 하는 실수부터, 코딩 테스트를 통과하기 위한 최적화 방법, 그리고 자바 내장 클래스 활용법까지 3단계로 나누어 완벽하게 정리해 보겠습니다.

---

1단계: 초보자의 접근 (배열 크기 직접 조절하기)

가장 먼저 떠올릴 수 있는 방법은 기본 배열(int[])을 만들고, 데이터가 들어오거나 나갈 때마다 배열의 크기를 늘렸다 줄였다 하는 것입니다.

public int[] makeStack(int[] arr) {
    int[] stk = {}; // 빈 배열
    
    for(int num : arr) {
        // 넣을 때: 기존 배열을 복사해서 1칸 더 큰 배열을 만듦
        stk = Arrays.copyOf(stk, stk.length + 1);
        stk[stk.length - 1] = num; // 마지막 방(길이 - 1)에 넣기
        
        // 뺄 때: 마지막 칸을 제외하고 복사해서 배열을 줄임
        // stk = Arrays.copyOfRange(stk, 0, stk.length - 1); 
    }
    return stk;
}

• 문제점: 논리적으로는 완벽하지만, 코딩 테스트에서는 100% '시간 초과'가 발생합니다. * 이유: Arrays.copyOf는 단순히 크기만 바꾸는 게 아니라, 매번 새로운 배열을 메모리에 만들고 기존 데이터를 하나씩 다 옮겨 적는 무거운 작업이기 때문입니다. (마치 짐을 하나 추가할 때마다 더 큰 집으로 이사를 가는 것과 같습니다.)

---

2단계: 고수들의 퍼포먼스 (인덱스 포인터 활용)

배열을 매번 새로 만들지 않고 속도를 극한으로 끌어올리려면 어떻게 해야 할까요?
바로 "처음부터 가장 큰 집을 구해놓고, 손가락(인덱스)으로 현재 위치만 가리키는 방식"을 사용해야 합니다.

public int[] fastStack(int[] arr) {
    // 1. 처음부터 원본 길이만큼 넉넉한 배열을 딱 1번만 만듭니다.
    int[] stk = new int[arr.length]; 
    
    // 2. 현재 스택의 꼭대기를 가리키는 손가락(top 포인터)
    int top = 0; 

    for (int num : arr) {
        if (top == 0 || stk[top - 1] != num) { 
            // 다르면 넣는다 (현재 손가락 위치에 덮어쓰고 1칸 전진)
            stk[top] = num; 
            top++;          
        } else {
            // 같으면 뺀다 (손가락을 1칸 뒤로 무름 -> 다음에 알아서 덮어씌워짐)
            top--;          
        }
    }
    
    // 3. 마지막에 손가락이 가리키는 곳까지만 딱 1번 잘라서 반환!
    return Arrays.copyOf(stk, top); 
}

• 장점: 배열 복사를 맨 마지막에 딱 1번만 하므로 속도가 압도적으로 빠릅니다. 코딩 테스트에서 실행 속도를 줄이고 싶을 때 강력 추천하는 방식입니다.

---

3단계: 자바의 정석 (Stack 클래스 활용)

사실 자바에는 이미 이 모든 것을 알아서 해주는 Stack 클래스가 존재합니다! 크기가 알아서 늘어나고 줄어들기 때문에, 우리는 push(넣기), pop(빼기), peek(맨 위 확인)이라는 직관적인 단어만 사용하면 됩니다.

import java.util.Stack;
import java.util.Arrays;

public int[] standardStack(int[] arr) {
    Stack<Integer> stack = new Stack<>(); 
    
    for (int num : arr) {
        // 스택이 비어있지 않고, 맨 위 숫자(peek)가 현재 숫자와 같으면 뺀다(pop)!
        if (!stack.isEmpty() && stack.peek() == num) {
            stack.pop();
        } 
        // 아니면 넣는다(push)!
        else {
            stack.push(num);
        }
    }
    
    // (꿀팁) 만들어진 Stack을 int 배열로 한 줄에 변환하기!
    return stack.stream().mapToInt(i -> i).toArray();
}

• 장점: 코드가 마치 사람이 말하는 것처럼 직관적으로 읽히며, 자잘한 인덱스 에러(IndexOutOfBounds)에서 완전히 해방됩니다!