[boj 9935] 폭발 문자열-js

메모리 초과로 고민 좀 했다..

 

내가 생각한 풀이 방법은 이렇다.

1. 폭발 문자열이 있다면 해당 문자열까지 배열에 삽입

2. 폭발 문자열 길이만큼 없앤 후 나머지 문자열 삽입 

3. 반복

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require('fs').readFileSync(filePath).toString().trim().split(/\n/);
const str = input.shift();
const target_str = input.shift();
const CLEARTEXT = "FRULA";
const sol = (str, target_str) =>{
    let arr = str.split('');
    let stk1 = [];
    
    while(str.indexOf(target_str) !== -1){
        for(let i=0; i<str.indexOf(target_str); i++){
            stk1.push(arr.shift());
        }
        for(let i=0; i<target_str.length; i++){
            arr.shift();
        }
        stk1.push(...arr);
        
        arr = stk1;
        str = stk1.join('');
        stk1 = [];
    }
    str === "" ? console.log(CLEARTEXT) : console.log(str);

}

sol(str, target_str);

뭔가 이게 맞아? 싶으면 다 안된다 ㅋㅋㅋ 메모리초과가 나타났다.

 

다음 풀이

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require('fs').readFileSync(filePath).toString().trim().split(/\n/);
const str = input[0];
const target_str = input[1];
const CLEARTEXT = "FRULA";
const sol = (str, target_str) =>{
    let arr = str.split('');
    let stk1 = [];
    
    for(let j=0; j<arr.length; j++){
        stk1.push(arr[j]);
        if(stk1.length>= target_str.length && stk1.join('').indexOf(target_str) !== -1){
            for(let i=0; i<target_str.length;i++){
                stk1.pop();
            }
        }
    }

    stk1.length ===0 ? console.log(CLEARTEXT) : console.log(stk1.join(''));
}

sol(str, target_str);

그렇다면 shift 연산을 할 때 실패를 했던 기억이 있어 shift를 없애고 push pop만 사용해보았다. 하지만 예상과 달리 메모리초과

 

생각해보니 shift는 메모리 초과보단 시간 초과의 경우였던 것 같다.

 

천천히 생각해본 결과 join과 indexOf부분 중 하나 일 것 같았다.

 

정답

const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const input = require('fs').readFileSync(filePath).toString().trim().split(/\n/);
const str = input[0];
const target_str = input[1];
const CLEARTEXT = "FRULA";
const sol = (str, target_str) =>{
    let arr = str.split('');
    let stk1 = [];
    
    for(let j=0; j<arr.length; j++){
        stk1.push(arr[j]);
        if(stk1.length>= target_str.length){
            let isBomb = true;
            for(let i=1; i<=target_str.length;i++){
                if(stk1[stk1.length-i] !== target_str[target_str.length - i]){
                    isBomb = false;
                }
            }
            if(isBomb){
                for(let i=0;i<target_str.length;i++){
                    stk1.pop();
                }
            }
        }
    }

    stk1.length ===0 ? console.log(CLEARTEXT) : console.log(stk1.join(''));
}

sol(str, target_str);

좋아좋아 

 

풀이는 이렇다

1. 문자열을 순서대로 스택에 푸시

2. 스택의 길이가 폭발 문자열과 같거나 큰가 비교 후 끝에서부터 차례대로 비교한다. (indexOf를 사용하지 않는 것이 포인트)

3. 만약 같다면 폭발문자열 길이만큼 pop 시킨다.

4 반복