Valid Parentheses

문제

괄호 기호인 '(', ')', '{', '}', '[', ']' 만으로 이루어진 문자열 s가 주어집니다. 이 문자열이 유효한 괄호 문자열인지 판별하는 프로그램을 작성하는 문제입니다. 유효한 문자열의 조건은 다음과 같습니다.

1. 열린 괄호는 같은 타입의 닫힌 괄호로 닫혀야 합니다.
2. 열린 괄호는 올바른 순서대로 닫혀야 합니다.
3. 모든 닫힌 괄호는 짝이 맞는 열린 괄호를 가지고 있어야 합니다.

• 입력: 괄호로만 이루어진 문자열 s (1 <= s.length <= 10^4)
• 출력: 유효한 문자열이면 true, 아니면 false 반환

링크: https://leetcode.com/problems/valid-parentheses

풀이: Stack과 조기 종료(Early Return)를 활용한 최적화

괄호의 짝을 맞추는 문제는 가장 나중에 열린 괄호가 가장 먼저 닫혀야 하는 후입선출(LIFO) 구조를 가지므로, Stack 자료구조를 사용하는 것이 가장 정석적이고 효율적입니다.

• 열린 괄호 처리: 문자열을 순회하면서 열린 괄호('(', '[', '{')를 만나면 무조건 스택에 넣습니다(push).
• 닫힌 괄호 처리 및 조기 종료: 닫힌 괄호를 만났을 때는 다음 로직을 거칩니다.
  • 예외 처리: 만약 스택이 비어있다면, 짝을 맞출 열린 괄호가 없는 것이므로 즉시 false를 반환합니다.
  • 짝 검증: 스택에서 최상단 요소를 꺼내어(pop) 현재 닫힌 괄호와 짝이 맞는지 비교합니다. 만약 종류가 다르다면 유효하지 않은 문자열이므로 더 이상 탐색할 필요 없이 즉시 false를 반환합니다 (조기 종료).
• 최종 검증: 문자열 순회가 끝난 후 스택이 완전히 비어있다면(st.isEmpty()) 모든 괄호가 올바르게 짝을 맞춰 제거된 것이므로 true를 반환하고, 남아있는 괄호가 있다면 false를 반환합니다.

코드

import java.util.*;

class Solution {
    public boolean isValid(String s) {
        Stack<Character> st = new Stack<>();

        for (char c : s.toCharArray()) {
            // 1. 열린 괄호는 스택에 추가
            if (c == '(' || c == '[' || c == '{') {
                st.push(c);
            } 
            // 2. 닫힌 괄호 처리
            else {
                // 스택이 비어있으면 짝을 맞출 수 없으므로 즉시 실패
                if (st.isEmpty()) {
                    return false;
                }

                // 최상단 요소를 꺼내어 현재 닫힌 괄호와 비교
                char top = st.pop();
                if (c == ')' && top != '(') {
                    return false;
                }
                if (c == ']' && top != '[') {
                    return false;
                }
                if (c == '}' && top != '{') {
                    return false;
                }
            }
        }

        // 3. 모든 순회 후 스택이 비어있으면 유효한 괄호
        return st.isEmpty();
    }
}

알고리즘 분류

자료 구조 (Data Structures), 스택 (Stack), 문자열 (String)