자료구조 · 알고리즘 기초집LESSON 06

스택: 실행 취소와 괄호 검증 문제

난이도초급 → 중급 입문

예상 시간40분

선수지식이전 강의

06강. 스택: 실행 취소와 괄호 검증 문제

1. 이번 강의에서 해결할 문제

가장 최근에 적용한 점수 변경부터 되돌리거나 가장 안쪽 괄호부터 맞추려면 입력 순서와 반대 순서로 처리해야 합니다.

2. 학습 목표

3. 핵심 개념

스택은 마지막에 들어온 값이 먼저 나오는 LIFO 구조입니다. Java의 오래된 Stack 클래스보다 Deque 계약과 ArrayDeque 구현을 사용하면 앞쪽에서 push, pop, peek를 표현할 수 있습니다. 실행 취소 기록, 함수 호출, 괄호 짝 검사에 적합합니다.

4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/StackValidator.java

src/StackValidator.java
import java.util.ArrayDeque;
import java.util.Deque;

public class StackValidator {
    static boolean isBalanced(String text) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : text.toCharArray()) {
            if (ch == '(' || ch == '[' || ch == '{') stack.push(ch);
            else if (ch == ')' || ch == ']' || ch == '}') {
                if (stack.isEmpty()) return false;
                char open = stack.pop();
                if ((open == '(' && ch != ')') || (open == '[' && ch != ']')
                        || (open == '{' && ch != '}')) return false;
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        System.out.println(isBalanced("stage[2](score{1200})"));
        System.out.println(isBalanced("stage[(])"));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/StackValidator.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/StackValidator.java와 out 아래 생성되는 class 파일

Windows PowerShell
Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\StackValidator.java
java -cp .\out StackValidator

예상 결과: 올바른 식은 true, 순서가 어긋난 식은 false가 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

5. 코드와 알고리즘이 동작하는 이유

여는 괄호를 스택에 쌓고 닫는 괄호가 나오면 가장 최근 괄호와 비교합니다. 각 문자를 한 번 처리해 O(n) 시간이며 모두 여는 괄호인 경우 O(n) 추가 공간을 사용합니다. 불일치를 발견하면 즉시 끝나는 최선은 O(1)입니다.

6. 자주 하는 실수와 해결법

7. 직접 실습

8. 이해 점검 질문 3개

9. 핵심 요약

MINI QUIZ