코딩 테스트 연습/LeetCode

[LeetCode] Valid Parentheses

은돌1113 2024. 7. 2. 13:05

문제 설명

주어진 문자열 s가 '(', ')', '{', '}', '[', ']' 문자들만 포함하고 있을 때, 이 문자열이 유효한지 판별하는 문제입니다.

 

유효한 문자열의 조건은 다음과 같습니다:

  1. 열린 괄호는 동일한 종류의 닫힌 괄호에 의해 닫혀야 합니다.
  2. 괄호는 올바른 순서로 닫혀야 합니다.
  3. 각 닫힌 괄호는 해당하는 종류의 열린 괄호가 있어야 합니다.

예를 들어, 문자열 "()"은 유효하며, "{}[]" 역시 유효합니다. 하지만 "{[}]"는 유효하지 않습니다.

이를 위해 스택(Stack) 자료구조를 사용하여 간단히 구현할 수 있습니다. 스택을 사용하면 괄호의 열림과 닫힘을 쉽게 추적하고 유효성을 검사할 수 있습니다.


입출력 예


입출력 예 #1

  • 입력 : s = "()"
  • 출력 : true

 

입출력 예 #2

  • 입력 : s = "()[]{}"
  • 출력 : true

 

입출력 예 #3

  • 입력 : s = "(]"
  • 출력 : false

문제풀이

var isValid = function (s) {
    const obj = {
        '(': ')',
        '[': ']',
        '{': '}',
    };

    let stack = [];

    for (let i = 0; i < s.length; i++) {
        const char = s[i];

        if (obj[char]) {
            stack.push(char);
        } else {
            const top = stack.pop();

            if (obj[top] !== char) {
                return false;
            }
        }
    }

    return stack.length === 0;
};

링크

 

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