코딩테스트 스택 풀이: 올바른 괄호 검증하기

내가 푼 풀이

문자열을 순회하면서 여는 괄호는 배열에 저장하고, 닫는 괄호가 나오면 하나씩 제거하는 방식으로 접근했습니다. 중간에 제거할 대상이 없으면 바로 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 구조로 역할이 분리되어 있어, 코드만 읽어도 괄호 처리 흐름이 자연스럽게 이해됩니다. 내 풀이는 조건이 분산되어 있어 흐름을 따라가야만 의도를 파악할 수 있습니다.

③ 예외 케이스 안정성

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

④ 코딩테스트 관점의 평가

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

괄호 기반 스택 응용을 더 넓혀보려면 JS 쇠막대기 스택 레이저 절단을 함께 보시면 좋습니다.

연산 우선순위를 다루는 유형은 JS 후위식 연산 스택 계산에서도 확인해두면 유사 패턴 정리가 쉬워집니다.

스택 불변식과 실패 케이스 검증

순회 중 스택에는 아직 짝을 찾지 못한 여는 괄호만 있어야 합니다. 닫는 괄호를 만났을 때 스택이 비어 있으면 바로 실패하고, 끝까지 읽은 뒤 스택이 비어 있어야 성공입니다. 이 두 검사를 분리하면 )(처럼 총개수는 같아도 순서가 잘못된 입력과 (()처럼 여는 괄호가 남은 입력을 모두 잡을 수 있습니다.

console.assert(solution('(()())') === 'YES');
console.assert(solution(')(') === 'NO');
console.assert(solution('(()') === 'NO');
console.assert(solution('') === 'YES');

소괄호 한 종류만 판별할 때는 숫자 카운터만으로도 같은 불변식을 O(1) 추가 공간에 표현할 수 있습니다. ()[]{}처럼 종류가 여러 개라면 최근 여는 괄호의 종류까지 확인해야 하므로 스택이 자연스럽습니다. push()와 pop()의 변경·반환 규칙은 MDN push()와 pop() 문서에서 확인하세요.

function solutionWithCount(s) {
  let open = 0;
  for (const ch of s) {
    if (ch === '(') open += 1;
    else if (ch === ')') open -= 1;
    else return 'NO';
    if (open < 0) return 'NO';
  }
  return open === 0 ? 'YES' : 'NO';
}

카운터 버전에서도 중간의 open < 0 검사를 생략하면 )(를 잘못 통과시킬 수 있습니다. 마지막 값만 0인지 보는 것과 순회 중 한 번도 음수가 되지 않았는지를 함께 확인해야 ‘모든 접두 구간에서 여는 괄호 수가 닫는 괄호 수 이상’이라는 조건이 성립합니다.

현재 정답 코드는 문제 조건상 입력 문자가 ( 또는 )뿐이라는 전제를 사용해 else를 모두 닫는 괄호로 처리합니다. 범용 검증기라면 다른 문자를 무시할지 오류로 볼지 먼저 정하고 분기해야 합니다. 공백이나 설명 문자가 섞인 문자열을 받는다면 괄호만 필터링할지 전체 입력을 거부할지도 같은 계약에 포함합니다.

정리: 성공 예제 하나보다 ‘중간에 먼저 닫힘’과 ‘마지막에 남음’을 각각 테스트하는 것이 중요합니다. 단일 괄호는 카운터, 여러 괄호는 스택이라는 선택 기준까지 설명하면 풀이 의도가 선명해집니다. 빈 문자열을 올바른 괄호열로 볼지도 문제 정의에 포함하며, 현재 구현은 YES를 반환합니다.