[JS 알고리즘] 올바른 괄호 문제 풀이 – 스택으로 순서 검증하기

• 문제
• 내가 푼 풀이
• 해답
• 내 풀이와 정답 풀이의 차이점
• FAQ

문제

괄호가 입력되면 올바른 괄호이면 “YES”, 올바르지 않으면 “NO”를 출력합니다.

예를 들어 (()())는 괄호의 쌍이 올바르게 위치하는 경우이지만, (()()는 올바른 괄호가 아닙니다.

입력 설명

첫 번째 줄에 괄호 문자열이 입력됩니다. 문자열의 최대 길이는 300입니다.

출력 설명

첫 번째 줄에 YES 또는 NO를 출력합니다.

입력 예제 1

(()())(()

출력 예제 1

NO

내가 푼 풀이

문자열을 순회하면서 여는 괄호는 배열에 저장하고, 닫는 괄호가 나오면 하나씩 제거하는 방식으로 접근했습니다. 중간에 제거할 대상이 없으면 바로 NO를 반환하도록 구성했습니다.

function solution(s) {
  let stack = [];
  let arr = s.split('');

  for (let x of arr) {
    if (x === '(') stack.push('(');
    if (stack.length === 0) return 'NO';
    if (x === ')') stack.pop();
  }

  return stack.length === 0 ? 'YES' : 'NO';
}

해답

아래 코드는 이 문제의 표준적인 정답 풀이입니다. 스택을 사용해 괄호의 순서를 검증하며, 닫는 괄호를 만났을 때 즉시 유효성을 판단하는 구조입니다.

function solution(s) {
  let answer = "YES";
  let stack = [];

  for (let x of s) {
    if (x === '(') {
      stack.push(x);
    } else {
      if (stack.length === 0) return "NO";
      stack.pop();
    }
  }

  if (stack.length > 0) return "NO";
  return answer;
}

1단계 – 여는 괄호 처리

if (x === '(') stack.push(x);

여는 괄호를 만나면 스택에 저장합니다. 이 시점에서는 올바른지 판단하지 않습니다.

2단계 – 닫는 괄호 검증

if (stack.length === 0) return "NO";

닫는 괄호가 나왔는데 스택이 비어 있다면, 앞에 짝이 없다는 의미이므로 즉시 NO를 반환합니다.

3단계 – 짝 제거

stack.pop();

검증을 통과한 경우, 가장 최근에 쌓인 여는 괄호를 제거하여 짝을 맞춥니다.

4단계 – 최종 상태 확인

if (stack.length > 0) return "NO";

모든 문자를 처리한 뒤에도 스택에 여는 괄호가 남아 있다면 올바르지 않은 괄호 문자열입니다.

내 풀이와 정답 풀이의 차이점

① 검증 시점의 차이

내 풀이에서는 반복문 안에서 스택이 비어 있는지를 매번 확인합니다. 이로 인해 여는 괄호를 처리한 직후에도 불필요한 검증이 수행됩니다. 반면 정답 풀이는 닫는 괄호를 만났을 때만 검증을 수행하여 논리가 더 명확합니다.

② 조건 분기의 명확성

정답 풀이는 if (x === '(') 와 else 구조로 역할이 분리되어 있어, 코드만 읽어도 괄호 처리 흐름이 자연스럽게 이해됩니다. 내 풀이는 조건이 분산되어 있어 흐름을 따라가야만 의도를 파악할 수 있습니다.

③ 예외 케이스 안정성

정답 풀이는 닫는 괄호가 먼저 등장하는 경우, 중간에 스택이 비는 경우, 마지막에 여는 괄호가 남는 경우를 각각 자연스럽게 처리합니다. 이는 조건을 단계별로 나눈 구조 덕분입니다.

④ 코딩테스트 관점의 평가

두 풀이 모두 정답 처리는 가능하지만, 정답 풀이는 면접이나 코딩테스트에서 의도와 사고 과정이 명확하게 드러나는 코드라는 점에서 더 좋은 평가를 받을 수 있습니다.

FAQ

Q. 괄호의 개수만 같으면 정답 아닌가요?
괄호 문제의 핵심은 개수가 아니라 순서입니다. 닫는 괄호가 먼저 나오면 올바르지 않습니다.

Q. 스택 없이도 풀 수 있나요?
이 문제는 스택을 사용하는 것이 가장 직관적이며, 다른 방식은 오히려 예외 처리가 복잡해집니다.

Q. 시간 복잡도는 어떻게 되나요?
문자열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다.