[백준 3986] 좋은 단어 with Node.js

문제 링크

www.acmicpc.net/problem/3986

3986번: 좋은 단어

풀이

const [N, ...arr] = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
let count = 0;
for (let word of arr) {
    if (word.length % 2 === 0) {
        let prevWord = word;
        let isGoodWord = true;
        while (prevWord) {
            const newWord = prevWord.replace(/A{2}|B{2}/g, "");
            if (newWord === prevWord) {
                isGoodWord = false;
                break;
            }
            prevWord = newWord;
        }
        if (isGoodWord) count++;
    }
}
console.log(count);

"좋은 단어"가 되려면 AABB처럼 같은 알파벳이 두 개씩 짝지어 붙어있거나, ABBA처럼 서로 떨어진 알파벳(A와 A) 사이에 있는 알파벳들(BB)이 이미 모두 짝이 지어진 상태여야 한다.

 

AA, BB처럼 이미 두 개씩 인접하여 짝지어진 알파벳들을 더 이상 제거할 수 없을 때까지 제거했을 때 남아 있는 알파벳이 존재하지 않는다면 좋은 단어이다. 예를 들어, AABB의 경우 두 개씩 인접하여 짝지어진 알파벳들로만 이루어져 있으므로 AA를 제거하고 남은 BB도 제거가 가능하다. ABBA의 경우 BB를 먼저 제거하면 AA가 남으므로 역시 제거할 수 있다. ABAABABBBAAB의 경우 바로 보이는 AA, BB, AA를 제거하면 ABBABB가 되고, 여기서 또 BB 두 개를 제거하면 AA가 되어 모두 제거할 수 있으므로 좋은 단어다.

 

또한 반드시 2개씩 짝지어야 하므로, 길이가 홀수인 단어는 좋은 단어가 될 수 없다.

 

정규표현식을 사용하여 "AA"와 "BB"를 찾아 빈 문자로 만들어서 최종적으로 빈 문자가 될 때까지 반복한다. 빈 문자가 된다면 좋은 단어이다. 하지만 만약 아직 모든 문자가 제거되지 않았는데도 replace한 결과가 하기 전과 동일하다면 ABAB처럼 더 이상 문자를 제거할 수 없는 상태이므로 좋은 단어가 아니게 된다.

 

이 문제는 스택을 이용하여 푸는 문제인데, 정규표현식이 먼저 떠올라서 이렇게 풀었다.

스택을 활용하여 풀려면, 스택에 단어의 알파벳들을 순회하면서 스택의 가장 위에 있는 알파벳과 다른 알파벳이면 추가하고, 같은 알파벳이면 추가하지 않고 오히려 가장 위에 있는 알파벳을 제거해서 최종적으로 스택이 비어있다면 좋은 단어가 된다.

const [N, ...arr] = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
let count = 0;
for (let word of arr) {
    const stack = [];
    for (let letter of word) {
        if (stack.length && stack[stack.length-1] === letter) {
            stack.pop();
        } else {
            stack.push(letter);
        }
    }
    if (stack.length === 0) count++;
}
console.log(count);