99클럽 코테 스터디 7일차 TIL - 쇠막대기 (스택)

문제: https://www.acmicpc.net/problem/10799
알고리즘 분류: 자료 구조, 스택

문제 파악

괄호로 표현된 쇠막대기와 레이저의 배치를 해석하는 문제

• ( 와 ) 가 인접한 경우는 레이저를 의미

• 나머지 (는 쇠막대기의 시작, )는 쇠막대기의 끝을 의미

• 레이저는 쇠막대기를 자르며, 쇠막대기는 자신을 지나는 레이저의 수 + 1만큼 조각으로 나뉨

• 최종적으로 잘려진 쇠막대기 조각의 총 개수를 구하자

접근 방법: 스택(Stack)

1. 문자열을 왼쪽에서 오른쪽으로 순회

2. (를 만나면: 스택에 넣는다 (잠재적인 쇠막대기 시작 또는 레이저 시작)

3. )를 만나면:

• 직전 문자가 (였다면: 이는 레이저를 의미
  → 스택에서 (를 pop하고, 현재 스택에 남아있는 (의 개수만큼 조각이 생김
• 직전 문자가 (가 아니었다면: 이는 쇠막대기의 끝을 의미
  → 스택에서 (를 pop하고, 조각 개수를 1 증가

내 코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
let answer = 0;
let stack = [];
let prevChar = '';

for (let char of input) {
    if (char === '(') {
        stack.push(char);
    } else { // 닫는 괄호인 경우
        stack.pop();

        if (prevChar === '(') {
            // 레이저인 경우
            answer += stack.length;
        } else {
            // 막대기 끝인 경우
            answer += 1;
        }
    }
    prevChar = char;
}
console.log(answer);

참고
https://bedecked-operation-4d1.notion.site/99-7-TIL-10799-Stack-1cfeb405261e8067bebdc807a89a6112