코딩테스트 스택 풀이: 쇠막대기 레이저 절단 개수 세기

스택을 사용하는 이유

이 문제는 괄호의 중첩 구조를 정확하게 처리해야 하기 때문에
스택(Stack) 자료구조를 사용하는 것이 가장 적합합니다.

여는 괄호 “(“를 만나면 스택에 push하여 쇠막대기의 시작을 기록하고,
닫는 괄호 “)”를 만나면 스택에서 pop하여 쇠막대기의 종료를 처리합니다.

이때 핵심 포인트는 현재 닫는 괄호가
레이저인지, 쇠막대기의 끝인지를 구분하는 것입니다.
이를 위해 바로 이전 문자(s[i – 1])를 함께 확인합니다.

특히 레이저는 쇠막대기 하나를 끝내는 개념이 아니라,
해당 시점에 열려 있는 모든 쇠막대기를 동시에 자르는 역할을 합니다.
따라서 레이저를 만났을 때는 현재 스택에 남아 있는 여는 괄호의 개수만큼
새로운 쇠막대기 조각이 한 번에 추가됩니다.

자바스크립트 풀이 코드

아래 전체 코드를 solution.cjs에 저장합니다. 표준 입력에서 괄호 문자열 한 줄을 읽고 결과 정수 하나만 출력합니다.

const fs = require("node:fs");

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

  for (let i = 0; i < s.length; i++) {
    if (s[i] === '(') {
      stack.push('(');
    } else {
      stack.pop();

      if (s[i - 1] === '(') {
        answer += stack.length;
      } else {
        answer++;
      }
    }
  }

  return answer;
}


const input = fs.readFileSync(0, "utf8").trim();
console.log(solution(input));

코드 흐름 상세 풀이

이제 위에 작성한 코드를 기준으로, 코드가 어떤 순서와 의도로 동작하는지 한 줄씩 따라가며 살펴보겠습니다.
이 단계에서는 코드의 위치와 실제 동작 의미를 1:1로 연결하는 것을 목표로 합니다.

for (let i = 0; i < s.length; i++) {
  // 괄호 문자열을 왼쪽부터 순회
}

먼저 for 반복문을 통해 문자열 s를 왼쪽부터 끝까지 한 글자씩 순회합니다.
괄호 표현은 왼쪽에서 오른쪽 순서대로 레이저와 쇠막대기의 배치를 나타내므로,
이 순서를 그대로 따라가는 것이 문제 해결의 출발점입니다.

if (s[i] === '(') {
  stack.push('(');
}

① 여는 괄호 “(“를 만났을 때
이 코드는 새로운 쇠막대기가 시작되었음을 의미합니다.
아직 닫히지 않은 쇠막대기를 관리하기 위해 스택에 여는 괄호를 push 합니다.

이 시점의 stack.length에는 레이저의 시작 괄호도 잠시 포함될 수 있습니다. 실제 막대 수로 사용하는 시점은 닫는 괄호를 처리하며 레이저 자신을 pop한 다음입니다.

else {
  stack.pop();
}

② 닫는 괄호 “)”를 만났을 때
닫는 괄호를 만나면 가장 먼저 stack.pop()을 수행합니다.
이는 레이저이든 쇠막대기의 끝이든 관계없이,
하나의 여는 괄호에 대한 처리는 공통적으로 종료되기 때문입니다.

if (s[i - 1] === '(') {
  answer += stack.length;
}

③ 레이저인지 여부 판별
닫는 괄호 직전 문자가 여는 괄호라면 “()” 형태의 레이저입니다.
레이저는 쇠막대기 하나를 끝내는 것이 아니라,
현재 열려 있는 모든 쇠막대기를 동시에 절단합니다.

따라서 레이저를 만났을 때는
answer += stack.length를 통해
해당 시점에 겹쳐진 쇠막대기 수만큼 조각을 한 번에 추가합니다.

else {
  answer++;
}

④ 쇠막대기의 끝을 만났을 때
이전 문자가 닫는 괄호인 경우 이는 레이저가 아니라
쇠막대기의 오른쪽 끝을 의미합니다.
이때는 하나의 쇠막대기 조각이 완성되는 순간이므로
answer++로 조각 하나를 추가합니다.

위 과정을 문자열의 끝까지 반복하면,
모든 레이저와 쇠막대기의 배치를 정확히 반영한 결과가 누적됩니다.
최종적으로 answer에는 잘려진 쇠막대기 조각의 총 개수가 저장됩니다.

카운트 기반과 비교한 문자열 제거 흐름은 JavaScript 괄호문자제거 스택 문자열에서 정리해두면 좋습니다.

같은 스택 패턴의 기초 정렬은 JavaScript 올바른 괄호 스택 검증에서 단계적으로 이어집니다.

시간·공간 비용

괄호 수를 n이라 하면 각 문자를 한 번 처리하므로 통상적인 동적 배열 모델에서 시간은 O(n) 상환입니다. 위 코드는 열린 괄호를 실제 배열 스택에 저장하므로 최악 O(n) 추가 공간을 사용합니다. 표준 입력 문자열 저장도 O(n)이며, 조각 수와 반복 인덱스 및 출력 숫자 하나는 O(1)입니다. 입력과 스택을 합친 전체 저장 공간은 O(n)입니다. 열린 개수만 정수로 세는 다른 구현의 O(1) 추가 공간과 이 배열 구현을 혼동하지 않습니다.