백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 9935, 문자열 폭발 [자료구조, 스택]

백준/ Gold 4 문제 , 백준 Node.js 자바스크립트 9935, 문자열 폭발 [자료구조, 스택]

 

 

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

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

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

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

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

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

-------------------------------------------------------------------------------------------

난이도 체감 🧑‍💻
1. 최상
2. 상
3. 중
4. 하


이해도 🙆‍♂️
1. 완벽히 이해
2. 다소 헷갈리는 부분들이 있음
3. 이해 못함


덧붙일 말 🏷️
인형뽑기 문제를 스택으로 풀어봤다면 이 문제 풀이법이 잘 떠오를 것이다.

 

 

 

문제 출처 🏠

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

9935번: 문자열 폭발

 

 

 

 

요구사항 📋

1. 폭발하는 형태의 문자를 모두 제거하는 것이다.

2. 이때, 주의할 점은 한 번 제거로 끝나는 것이 아닌 제거 후 남은 문자열들 끼리 이으면 새로운 문자열에서 또 폭발 문자가 나올 수 있다. 

3. 다시 말해서 더이상 폭발 문자가 안나올때까지 계속적으로 제거해 나아가는 것이다.

 

 

해결 전략 📝

 

https://school.programmers.co.kr/learn/courses/30/lessons/64061

프로그래머스

 

 크레인 인형 뽑기 문제를 풀어본 경험이 있다면 이 문자열 폭발 문제를 봤을때 번뜩 떠오를 것이다.

 

푸는 원리가 굉장히 비슷하다. 

 

 

접근하는 법은 생각보다 간단한데, 스택을 이용하면 된다.

 

 

 

만약 ACCBB 라는 문자가 있다고 가정해보자.

 

이때, 폭발 문자열은 CB이다.

 

그러면 처음에 ACCBB 에서 ACCBB  빨간색 문자가 제거될 것이다.

 

그렇다면 AC   B 이렇게 남게된다.

 

다시, 이으면 ACB 가 되고 여기서 ACB 또 빨간색 문자가 제거되어 최종적으로 A만 남게된다.

 

 

이것을 O(n) 시간복잡도로 처리할 수 있는데,

 

스택에 하나씩 집어 넣어가면서 폭발 문자열이 만들어지면 바로 제거시켜버리는 것이다.

 

 

위의 과정을 나열해보면

 

 

1. A

 

2. AC

 

3. ACC

 

4. ACCB  => AC

 

5. ACB => A

 

이 순서대로 되는 것이다.

 

이 로직을 코드로 구현하면 된다.

 

 

 

반례 ⚠️

 

입력

1234

13

 

정답

1234

 

 

 

입력 

abcbbeegef
be

 

정답

abcgef

 

 

 

정답 💯

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

const [S, bomb] = input;

function solution(S, bomb) {
  let arr = [];
  let len = bomb.length;
  S.split("").map((v) => {
    if (arr.slice(arr.length - len + 1, arr.length).join("") + v === bomb) {
      for (let i = 0; i < len - 1; i++) arr.pop();
    } else arr.push(v);
  });
  return arr.length === 0 ? "FRULA" : arr.join("");
}

console.log(solution(S, bomb));