[백준 9935] 문자열 폭발 (String/Stack, 자바스크립트)

Jiyoung Park·2023년 2월 21일
0

Stack

목록 보기
1/1

문자열 폭발

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

  • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
  • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
  • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
    상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

풀이

  1. 자바스크립트의 replace 함수와 정규식을 이용해 풀이할 경우, n의 크기로 인해 메모리 초과가 난다.

  2. stack을 이용한 풀이
    stack의 index를 가리키는 idx 변수를 이용하여 stack[idx]에 문자열을 넣는다.

    stack의 끝 문자열과 폭발 문자열 exploe의 끝 문자열이 일치하면, 폭발 문자열인지 확인한다.

    문자열이 일치하면(폭발 문자열이라면) idxexploe.length만큼 앞으로 이동한다.

    폭발이 끝난 문자열을 0번 index부터 idx만큼 slicing한 결과가 남은 문자열이다.

코드

const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = require("fs").readFileSync(filePath).toString().trim().split("\n");

const str = input[0].trim();
const exploe = input[1].trim();
let n = exploe.length;
let stack = new Array(str.length).fill("");
let idx = 0;

for (let i=0; i<str.length; i++) {
    // 1. stack에 새로운 문자열을 넣는다.
    stack[idx++] = str[i];

    // 2. stack의 가장 뒤에 있는 문자열이 폭발 문자열과 일치하면 pop한다.
    //    (index를 이전으로 이동한다.)
    if (stack[idx-1] === exploe[n-1] && idx > n-1) {
        let flag = true;
        for (let j=1; j<n; j++) {
            if (stack[idx-1-j] != exploe[n-1-j]) {
                flag = false;
                break;
            }
        }
        if (flag) {
            idx -= n;
        }
    }


}

let result = stack.slice(0, idx).join("");
if (result === "") console.log("FRULA");
else console.log(result);

0개의 댓글