쇠막대기 (백준 코딩테스트 10799번, 스택(stack), NodeJS 풀이)

https://www.acmicpc.net/problem/10799

 

문제 유형:

스택

 

문제 요약:

'()'되어 있는 곳이 레이저로 자르는 곳.

그 이외의 괄호는 한 판때기의 시작점 혹은 끝점을 나타낸다.

레이저로 자른 판때기는 총 몇 개가 나오는가?

 

 

입출력 예 (입력 / 출력):

총 몇 개인지를 출력값으로 내보낸다.

 

 

문제 풀이 전략:

판때기의 시작점인 '('은 판이 현재 열마나 깔려있나를 보여주는 갯수이다.

판때기의 끝점인 ')'은 깔려있는 칸이 하나 줄어든다는 뜻이다. 그리고 잘리고 남은 나머지 조각 1개가 발생한다는 뜻이다.

레이저를 뜻하는 '()'은 현재까지 판때기가 얼마나 깔려있는지를 카운팅하라는 뜻으로 볼 수 있다.

 

이 문제는 stack을 이용해 풀 수 있다.

1. '('을 계속 카운팅하다가 '()'을 만났을 때 '('만큼 결과값에 더해준다.
2. ')'을 만나면
   1. 판때기가 하나 끝났다는 뜻으로 '('을 하나 빼준다.
   2. 판때기가 잘리고 남은 조각 1개가 있다는 뜻이니 결과값에 1 더해준다.

 

내 풀이:

let fs = require("fs");
let input = fs.readFileSync("dev/stdin").toString().trim().split("\n")[0];

const stack = [];
let cnt = 0;

const replaced = input.replaceAll("()", "_"); //'()'을 '_'로 변환하여 구분을 쉽게 해준다.

for (let i = 0; i < replaced.length; i++) {
  if (replaced[i] === "_") { // 만약 '_'가 나온다면
    cnt += stack.length; // '_'가 나오기 전에 '('가 있었던 갯수가 새로 생기는 조각의 갯수이다. 즉 stack에 들어있는 원소만큼 더해주면 된다. 
  } else if (replaced[i] === "(") { // '('일 시에는
    stack.push(replaced[i]); // 스택에 '('을 넣어준다.
  } else {
    stack.pop(); // ')'일시는 잘리고 남은 조각들이 발생한 것이기 때문에
    cnt++; // 1개 증가 시킨다.
  }
}
console.log(cnt); //총 갯수 표출