Valid Parentheses Explanation

Problem Summary

Write a function that checks if a string of parentheses is valid.

Detailed Explanation

이 문제는 **스택(Stack)** 자료구조를 활용한 괄호 검증 알고리즘을 학습합니다. 코딩 인터뷰의 클래식 문제입니다. **스택을 사용하는 이유** 괄호는 LIFO(Last In, First Out) 특성을 가집니다. 가장 최근에 열린 괄호가 먼저 닫혀야 합니다. **알고리즘 전략** 1. 여는 괄호 → 대응하는 닫는 괄호를 스택에 push 2. 닫는 괄호 → 스택에서 pop하여 일치 확인 3. 끝까지 순회 후 스택이 비어있으면 유효 **pairs 객체의 역할** `{ '(': ')', '[': ']', '{': '}' }` 여는 괄호를 키로, 대응하는 닫는 괄호를 값으로 매핑합니다. **"(())" 처리 과정** - '(' → stack=[')']; - '(' → stack=[')', ')'] - ')' → pop()=')' === ')' ✓ - ')' → pop()=')' === ')' ✓ - 스택 비어있음 → true **"([)]" 처리 과정** - '(' → stack=[')'] - '[' → stack=[')', ']'] - ')' → pop()=']' !== ')' → false! **왜 기대하는 닫는 괄호를 저장하는가?** 닫는 괄호를 만났을 때 바로 비교할 수 있어 코드가 간결해집니다.

Solution Code

solution.js

function isValid(str) {
  const stack = [];
  const pairs = { '(': ')', '[': ']', '{': '}' };
  for (const char of str) {
    if (pairs[char]) stack.push(pairs[char]);
    else if (stack.pop() !== char) return false;
  }
  return stack.length === 0;
}

Key Concepts from This Problem

1. 스택 자료구조

2. LIFO 원리

3. 괄호 매칭

4. 유효성 검사

Common Mistakes

✗ 닫는 괄호가 더 많으면 pop()이 undefined를 반환합니다

✗ 마지막에 스택이 비어있는지 확인해야 합니다

✗ 여러 종류의 괄호가 섞여 있을 때 짝이 맞아야 합니다

Hints

Hint 1: 스택을 사용하세요.

Hint 2: 여는 괄호는 푸시, 닫는 괄호는 팝하세요.

Complexity Analysis

Time Complexity

O(n)

Grows linearly with input size

Space Complexity

O(n)

Uses memory proportional to input size

Related Tags

#알고리즘 #스택 #괄호