좋은 단어 (백준 코딩테스트 3986번, 스택(stack), NodeJS 풀이)

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

 

문제 유형:

stack

 

문제 요약:

평석이는 단어 위로 아치형 곡선을 그어 같은 글자끼리(A는 A끼리, B는 B끼리) 쌍을 짓기로 하였다. 만약 선끼리 교차하지 않으면서 각 글자를 정확히 한 개의 다른 위치에 있는 같은 글자와 짝 지을수 있다면, 그 단어는 '좋은 단어'이다. 평석이가 '좋은 단어' 개수를 세는 것을 도와주자.

 

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

 

좋은 단어와 나쁜 단어 설명:

나쁜 단어는 A끼리, B끼리 연결 시켰을 때, 서로 교차하는 단어를 뜻한다.

좋은 단어는 겹치지 않는 단어이다.

이렇게 보면 회문을 찾으라는 문제처럼 생각할 수 있는데

이런 경우는 회문이 아니어도 중첩되지 않는다.

 

문제 풀이 및 전략:

예시로 보아 단지 A와 B가 교차해있다고 해서 나쁜 단어라고 할 수 없다.

A와 B가 교차해있더라도 A라는 커버 안에서 B가 다 짝이 맞아있다면 좋은 단어가 될 가능성이 있다.

A안에 B가 있다고 해도 B가 다 짝이 맞고, B안에 A가 있다고 해도 그 안에서 짝을 모두 찾을 수 있다면 그건 좋은 단어가 된다.

뭐랄까.. 뿌요뿌요를 생각해보면 된다. '뿌요뿌요 상에 있다면 이게 다 터져서 0이 될 수 있는가?'를 생각하면 된다. 

 

이런 구조를 코드로 옮기려면 스택을 활용해야 된다.

 

 

내 풀이:

let fs = require("fs");
let [totalNum, ...list] = fs.readFileSync("dev/stdin").toString().trim().split("\n");
//단어 리스트를 추출

let cnt = 0;
for (let i = 0; i < list.length; i++) { //리스트에서 뽑은 것을 검증하는 반복문
  let target = list[i]; //단어 리스트에서 한 단어를 뽑는다.
  const stack = []; // 스택을 활용할 것
  for (let j = 0; j < target.length; j++) {
    if (!stack.length) { // 스택에 아무것도 없는 경우엔
      stack.push(target[j]); // 스택에 push
    } else if (stack[stack.length - 1] === target[j]) { //스택의 마지막 글자가 방금 뽑은 글자와 같다면
      stack.pop(); //짝이 맞으니 없애준다.
    } else { // 마지막 글자가 방금 뽑은 글자랑 다르다면
      stack.push(target[j]); // 그냥 쌓는다.
    }
  }
  if (!stack.length) { // 이렇게 해서 stack에 아무것도 없다면 짝이 다 맞아 떨어진 '좋은 단어'이므로
    cnt++; // 카운트를 올려준다.
  }
}
console.log(cnt); // 카운트를 표출한다.