[Leet Code] 20. Valid Parentheses

https://leetcode.com/problems/valid-parentheses/description/

 

문제 설명

주어진 문자열 s는 '(', ')', '{', '}', '[', ']' 문자만으로 구성되어 있습니다.

이때, 문자열이 **올바른 괄호 문자열(valid parentheses)**인지 판별하세요.

 

문자열이 올바르다고 판단되는 조건은 다음과 같습니다:

1. 열린 괄호는 반드시 동일한 종류의 닫힌 괄호로 닫혀야 한다.
2. 예: (는 )로, [는 ]로, {는 }로만 닫을 수 있습니다.
3. 괄호는 올바른 순서대로 닫혀야 한다.
4. 중첩된 괄호는 구조적으로 올바른 순서를 유지해야 합니다.
5. 닫힌 괄호가 등장할 때, 반드시 해당하는 열린 괄호가 이전에 존재해야 한다.
6. 즉, 닫힌 괄호가 먼저 등장하면 올바르지 않은 문자열입니다.

 

접근 방식

LIFO(Last In First Out) 구조인 스택을 이용해서 풀어보자!

Stack (스택)

• LIFO(Last In, First Out) 구조
• 열린 괄호를 순서대로 넣어두고, 닫힌 괄호가 나올 때 pop하여 매칭 여부 판단
• 중첩 괄호 구조를 다루기 위한 최적의 자료구조

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Stack 생성
        Stack<String> stack = new Stack<>();

        // push: 데이터 넣기
        stack.push("A");
        stack.push("B");
        stack.push("C");

        System.out.println("현재 스택: " + stack);

        // pop: 맨 위 요소 꺼내기
        String top = stack.pop();
        System.out.println("pop한 값: " + top);
        System.out.println("pop 이후 스택: " + stack);

        // peek: 삭제 없이 맨 위 요소 보기
        String peek = stack.peek();
        System.out.println("peek 값: " + peek);

        // empty: 스택이 비었는지 확인
        System.out.println("스택이 비었나? " + stack.empty());
    }
}

Map (괄호 매핑 테이블)

닫힌 괄호가 등장했을 때 “이 괄호는 어떤 열린 괄호와 매칭되어야 하는가?“를 즉시 확인하기 위해 사용

')' → '('
']' → '['
'}' → '{'

 

알고리즘 흐름

1. 열린 괄호가 나오면 Stack에 push
2. 닫힌 괄호가 나오면 Stack에서 pop하여 매칭 검사
   
   • 스택이 비어 있다면 → 매칭할 열린 괄호가 없으므로 false 리턴
   • pop한 열린 괄호가 Map이 가진 매칭 괄호와 정확히 일치하는지 비교
   • 일치하지 않으면 즉시 false
3. 매칭이 하나라도 틀리면 즉시 false
4. 순회를 모두 마친 후 스택이 비어 있어야 valid
   
   • 비어 있다 → 모든 괄호가 정상적으로 닫힘 -> true 리턴 
   • 비어 있지 않다 → 열린 괄호가 남아 있음 → false 리턴

 

나의 풀이 코드

class Solution {
     public boolean isValid(String s) {
        Map<String, String> brackets = new HashMap<>();
        brackets.put("(", ")");
        brackets.put("{", "}");
        brackets.put("[", "]");

        Stack<String> stack = new Stack<>();

        if (s == null || s.length() < 2) {
            return false;
        } else {
            int length = s.length();

            for (int i = 0; i < length; i++) {
                String target = String.valueOf(s.charAt(i));

                if (brackets.containsKey(String.valueOf(s.charAt(i)))) {
                    stack.push(target);
                } else {
                    if (stack.isEmpty()) {
                        return false;
                    }

                    String close = brackets.get(stack.pop());
                    if (!close.equals(target)) {
                        return false;
                    }
                }
            }
        }

        return stack.isEmpty(); 
    }
}

 

리팩토링된 최종 코드

class Solution {
    public boolean isValid(String s) {
        // 매칭 테이블: 닫는 괄호 → 여는 괄호
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put('}', '{');
        map.put(']', '[');

        Stack<Character> stack = new Stack<>();

        for (char c : s.toCharArray()) {

            // 열린 괄호라면 push
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else { // 닫힌 괄호라면
                if (stack.isEmpty()) return false;

                char open = stack.pop();           // 마지막 열린 괄호
                char expected = map.get(c);        // 이 닫힌 괄호의 매칭되는 열린 괄호

                if (open != expected) return false; // 매칭 안 되면 invalid
            }
        }

        return stack.isEmpty(); // 모든 괄호가 정상적으로 닫혀야 valid
    }
}