백준/ Silver 4 문제 , 백준 Node.js 자바스크립트 3986 , 좋은 단어 [자료구조, 스택]

백준/ Silver 4 문제 , 백준 Node.js 자바스크립트 3986 , 좋은 단어 [자료구조, 스택]

 

 

Check Point !   ( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가?

-------------------------------------------------------------------------------------------
난이도 체감
1. 최상
2. 상
3. 중
4. 하


<이해도>
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


<덧붙일 말>
테트리스 게임 하듯이 하면 된다.

 

 

문제 출처

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

3986번: 좋은 단어

 

 

 

 

 

풀이

 

 

 

아치형 그런거 생각하지말고 그냥 같은 문자가 2개 붙어 있다면 지워나가서 최종적으로 남은 문자가 없어야 한다.

 

 

예를들면 

 

ABAABA  이렇게일때 

 

가운데 AA를지우면  ABBA 가 남는다. 

 

또 같은 문자 BB 를 지우면 AA 가 남고, 이 AA도 지우면 다 없어지게 되므로 문제에서 찾고자 하는 좋은 단어 조건에 부합한다.

 

 

 

방법은 이렇지만 한번에 지우기 보단. 차례대로 배열에 넣어가면서 같은 단어가 붙어지게 되면 바로바로 지워주는 것이 시간 복잡도가 O(n) 으로 더 간편한 연산이 가능하다.

 

 

해당 코드를 구현했을때의 과정이다.

 

 

각 단어를 확인해보고 조건에 부합하면 카운트 해준 뒤 최종적으로 카운트한 값만 출력해주자.

 

 

 

 

 

정답

 

const input = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((v) => v.trim());

const [T, ...words] = input;

function solution(T, words) {
  let result = 0;
  words.map((v) => {
    let arr = [];
    v = v.split("");
    for (let word of v) {
      if (arr[arr.length - 1] === word) arr.pop();
      else arr.push(word);
    }
    if (arr.length === 0) result += 1;
  });
  return result;
}
console.log(solution(T, words));