[LeetCode] 20. Valid Parentheses

LeetCode 문제 20. Valid Parentheses에 대한 나의 풀이 코드.

문제

• '(', ')', '{', '}', '[', ']' 문자만 포함하는 문자열 s가 주어지면 입력 문자열이 유효한지 확인합니다.

다음과 같은 경우 입력 문자열이 유효합니다.

1. 열린 괄호는 동일한 유형의 괄호로 닫혀야 합니다.
2. 열린 괄호는 올바른 순서로 닫혀야 합니다.
3. 모든 닫는 괄호에는 동일한 유형의 해당 열린 괄호가 있습니다.

처음 제출 코드

var isValid = function(s) {
  const bracketStack = [];
  const openBracketList = ['(', '{', '['];
  const closeBracketList = [')', '}', ']'];
  let answer = false;

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

    // 여는 괄호면
    if (openBracketList.includes(c)) {
      bracketStack.push(c);

      // 괄호가 열리면 다시 닫혀야 하기 때문에 false
      answer = false;
    } else { // 닫는 괄호면

      // 괄호의 짝을 찾음
      const bracketIndex = closeBracketList.findIndex(b => b === c);
      const pair = openBracketList[bracketIndex];

      // 스택의 마지막 값 확인
      const last = bracketStack[bracketStack.length - 1];

      // last가 없음 -> stack의 length가 1임 (괄호 성립 안됨)
      // pair !== last -> 짝이 안맞음 바로 break;
      if (!last || pair !== last) {
        answer = false;
        break;
      } else {
        // 짝이 맞으면 스택에서 빼냄
        bracketStack.pop();
        answer = true;

        // 빼냈는데 stack에 아직 뭔가 남아 있으면 다시 돌아야 하므로 false
        if (bracketStack.length > 0) answer = false;
      }
    }
  }
  return answer;
};

처음에는 괄호가 열리면 열린 괄호를 stack에 넣고, 닫힌 괄호를 만났을 때 그 짝에 맞는 열린 괄호가 stack에 있는지 확인했다.

통과는 했지만 stack을 제대로 이용하지 않은 것 같아 찝찝해서 제출 후 다른 사람의 풀이를 봤다.

최종 제출 코드

역시나 더 간단해 질 수 있었다. 처음과 반대로 생각해서 stack에 열린 괄호가 아닌 닫힌 괄호를 넣으면 더 간단해질 수 있었다.

var isValid = function(s) {
  const bracketStack = [];
  const bracketPair = {
    "(": ")",
    "[": "]",
    "{": "}"
  }
  for (const c of s) {
    if (bracketPair[c]) {
      bracketStack.push(bracketPair[c]);
    } else {
      const last = bracketStack.pop();
      if (c !== last) return false;
    }
  }
  return bracketStack.length === 0;
};