[LeetCode] Valid Parentheses

🧑‍💻 언어 및 제출 결과

• 사용 언어: TypeScript, ...
• 통과 여부: ✅

🧠 풀이 설명

첫 번째 시도

괄호가 잘 닫혔는지 판별하는 문제입니다.
우선 괄호의 개수가 짝수가 아니면 false를 반환하고, 첫 번째 괄호가 닫힌 괄호면 false를 반환합니다.
그 뒤 괄호를 하나씩 확인하면서 열린 괄호는 스택에 추가하고, 닫힌 괄호는 스택에서 마지막 요소를 확인해서 짝이 맞는지 확인합니다.
짝이 맞지 않으면 false를 반환하고, 짝이 맞으면 스택에서 마지막 요소를 제거합니다.
stack에 남는게 없다면 괄호가 잘 닫힌 것이고, 남는게 있다면 괄호가 잘 닫히지 않은 것입니덩
())) 케이스에서 true를 뱉어 버리는 문제가 있어 fail 했습니다.

const isValid = (s: string): boolean => {
  if (s.length % 2 !== 0) return false;

  const stack: string[] = [];

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

    if (i === 0 && (char === ")" || char === "]" || char === "}")) return false;

    if (char === "(" || char === "[" || char === "{") {
      stack.push(char);
    }

    if (char === ")" || char === "]" || char === "}") {
      const last = stack.pop();
      if (last === "(" && char !== ")") return false;
      if (last === "[" && char !== "]") return false;
      if (last === "{" && char !== "}") return false;
    }
  }

  return stack.length === 0;
};

---

두 번째 시도

첫 번째 시도에서 첫 번째 괄호가 닫힌 괄호면 false를 반환하는 부분을 제거하고 last가 없는 경우에 false를 반환하도록 수정했습니다.
이렇게 하면 첫 번째 괄호가 닫힌 괄호면 false를 반환하고, 괄호가 잘 닫히지 않아도 false를 반환하게 됩니다.

const isValid = (s: string): boolean => {
  if (s.length % 2 !== 0) return false;

  const stack: string[] = [];

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

    if (char === "(" || char === "[" || char === "{") {
      stack.push(char);
    }

    if (char === ")" || char === "]" || char === "}") {
      const last = stack.pop();
      if (!last) return false;

      if (last === "(" && char !== ")") return false;
      if (last === "[" && char !== "]") return false;
      if (last === "{" && char !== "}") return false;
    }
  }

  return stack.length === 0;
};

📊 시간/공간 복잡도

✅ 어떠한 근거로 시간/공간 복잡도가 이렇게 나왔는지 설명해주세요.

⚡️ 풀이의 속도와 메모리 등을 캡쳐해서 올려주세요.

• 시간 복잡도: O(n)
• 공간 복잡도: O(n)