스택을 이용한 괄호 유효성 검사: 접근 방식과 해결 과정

문제 설명

여러 종류의 괄호로 이루어진 문자열이 주어졌을 때, 이 문자열의 괄호가 올바르게 열리고 닫혔는지 확인하는 프로그램을 작성하세요.

괄호의 종류는 다음과 같습니다.

소괄호: (, )
중괄호: {, }
대괄호: [, ]

예시

입력: "({[()]})"
출력: True (올바른 괄호 열림과 닫힘)
입력: "([)(])"
출력: False (잘못된 괄호 열림과 닫힘)

문제 분석

이 문제를 해결하기 위해서는 괄호의 열림과 닫힘이 올바른 순서로 이루어졌는지 검사해야 합니다. 이를 위해 스택(Stack) 자료구조를 사용하면 효율적으로 해결할 수 있습니다.

스택의 특성

후입선출(Last In First Out, LIFO) 구조입니다.
마지막에 추가된 요소가 가장 먼저 제거됩니다.
괄호의 열림과 닫힘을 처리하기에 적합합니다.

단계별 해결 과정

1. 스택 초기화

빈 스택을 생성합니다.
문자열의 문자를 하나씩 검사하면서 괄호의 열림과 닫힘을 처리합니다.

2. 문자열 순회

문자열의 각 문자를 순서대로 확인합니다.

2.1. 여는 괄호인 경우

여는 괄호 (, {, [ 중 하나이면 스택에 추가합니다.

2.2. 닫는 괄호인 경우

닫는 괄호 ), }, ] 중 하나이면 스택에서 요소를 꺼내어 짝이 맞는지 확인합니다.
스택이 비어있으면 유효하지 않은 괄호입니다.
스택에서 꺼낸 여는 괄호와 현재 닫는 괄호가 짝이 맞지 않으면 유효하지 않은 괄호입니다.

3. 순회 완료 후 스택 확인

문자열 순회를 완료한 후 스택이 비어 있으면 올바른 괄호입니다.
스택에 요소가 남아 있으면 유효하지 않은 괄호입니다.

구현 코드

import java.util.Stack;

public class ParenthesisValidator {
    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        // 괄호의 매칭을 위한 맵핑
        Map<Character, Character> brackets = new HashMap<>();
        brackets.put(')', '(');
        brackets.put('}', '{');
        brackets.put(']', '[');

        for (char c : s.toCharArray()) {
            // 여는 괄호인 경우 스택에 추가
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            }
            // 닫는 괄호인 경우 스택에서 꺼내어 비교
            else if (c == ')' || c == '}' || c == ']') {
                if (stack.isEmpty() || stack.pop() != brackets.get(c)) {
                    return false;
                }
            }
            // 괄호가 아닌 다른 문자일 경우 (이 문제에서는 없다고 가정)
            else {
                // 필요한 경우 처리
            }
        }
        // 스택이 비어 있으면 올바른 괄호
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String input1 = "({[()]})";
        String input2 = "([)(])";

        System.out.println("입력: " + input1);
        System.out.println("출력: " + isValid(input1)); // True

        System.out.println("입력: " + input2);
        System.out.println("출력: " + isValid(input2)); // False
    }
}

코드 설명

스택 초기화: Stack<Character> stack = new Stack<>();
괄호 매핑: 닫는 괄호와 여는 괄호를 매핑하기 위해 HashMap을 사용합니다.
문자 순회:
- 여는 괄호이면 스택에 추가합니다.
- 닫는 괄호이면 스택에서 요소를 꺼내어 매핑된 여는 괄호와 일치하는지 확인합니다.
- 일치하지 않으면 false를 반환합니다.
결과 반환:
- 순회가 끝난 후 스택이 비어 있으면 true를 반환합니다.
- 스택에 요소가 남아 있으면 false를 반환합니다.

추가 예제 및 테스트

public static void main(String[] args) {
    String[] testInputs = {
        "()",        // True
        "({[]})",    // True
        "({[}])",    // False
        "(",         // False
        ")",         // False
        "",          // True
        "([{}])()",  // True
        "[(])",      // False
        "{[()()]}",  // True
        "{[(])}",    // False
    };

    for (String input : testInputs) {
        System.out.println("입력: " + input + " -> 출력: " + isValid(input));
    }
}

출력 결과:

입력: () -> 출력: true
입력: ({[]}) -> 출력: true
입력: ({[}]) -> 출력: false
입력: ( -> 출력: false
입력: ) -> 출력: false
입력:  -> 출력: true
입력: ([{}])() -> 출력: true
입력: [(]) -> 출력: false
입력: {[()()]} -> 출력: true
입력: {[(])} -> 출력: false

시간 및 공간 복잡도 분석

시간 복잡도: O(n)
- 문자열의 길이에 비례하여 한 번의 순회를 수행하므로 선형 시간 복잡도입니다.
공간 복잡도: O(n)
- 최악의 경우 모든 문자가 여는 괄호이면 스택에 모두 저장되므로 선형 공간 복잡도입니다.

확장 및 응용

다른 종류의 괄호 추가: 만약 <와 > 같은 괄호를 추가하고 싶다면 매핑에 추가하면 됩니다.
괄호 외의 문자 처리: 괄호 외에 다른 문자가 포함된 문자열에서도 괄호의 유효성을 검사할 수 있도록 수정할 수 있습니다.
에러 위치 표시: 유효하지 않은 경우 어디에서 오류가 발생했는지 위치를 반환하도록 개선할 수 있습니다.

마무리

이번 글에서는 스택을 활용하여 괄호의 유효성을 검사하는 방법을 알아보았습니다. 스택은 데이터의 순서를 관리하는 데 유용한 자료구조로, 괄호 문제 외에도 다양한 알고리즘에서 활용됩니다. 이 문제를 통해 스택의 기본 개념과 활용 방법을 이해하는 데 도움이 되었기를 바랍니다.

학습 포인트:

스택 자료구조의 이해: 후입선출 구조를 이해하고, 스택의 기본 연산인 push와 pop을 익힙니다.
문제 해결 능력 향상: 복잡한 문제를 단순화하고, 적절한 자료구조를 선택하여 효율적으로 해결하는 방법을 배웁니다.
코드 구현 능력 향상: 자바에서 스택을 사용하는 방법과 예외 처리를 익힙니다.

앞으로도 다양한 알고리즘과 자료구조를 공부하며 프로그래밍 실력을 향상시켜 보세요. 궁금한 점이나 도움이 필요한 부분이 있다면 언제든지 문의해주세요!

추가 팁:

자료구조 선택의 중요성: 문제에 적합한 자료구조를 선택하면 코드가 간결해지고 효율성이 높아집니다.
코딩 테스트 대비: 괄호 유효성 검사는 코딩 테스트에서 자주 등장하는 유형이므로 숙지해두면 도움이 됩니다.
연습 문제 풀기: 다양한 입력과 예외 케이스를 스스로 만들어보고 코드를 테스트해보세요.

세미콜론 코딩학원