백준 온라인 저지/출제된 문제/9935(r3 판)

상위 문서: 백준 온라인 저지/출제된 문제

문자열 폭발
문제 번호		9935
기여자		목록 확인
레이팅		Gold IV
알고리즘		More 자료 구조 문자열 스택

1. 개요2. 풀이3. 정답 코드

3.1. Javascript

1. 개요 [편집]

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

두 줄에 걸쳐서 문자열과 폭발 문자열이 주어지며, 폭발 문자열을 제외한 문자열을 출력하는 문제다. Gold IV에 해당하는 다소 어려운 문제로, 처음 생각한 방법대로 시도했다가는 높은 확률로 시간 초과 오류를 경험하게 된다.

2. 풀이 [편집]

간단해보이는 문제에 비해 높은 티어를 보고 눈치챘겠지만 많은 언어에서 기본적으로 제공하는 문자열 치환 함수만 가지고는 제한 시간 안에 문제를 풀 수 없다. 이 방법으로 시도하기에는 함수의 시간 복잡도 (Javascript 기준

O_{(n)}

) 때문에 100% 시간 초과 오류가 난다.

따라서 문자"열"도 배열이라는 사실을 인지하고, 스택의 개념으로 접근하는 것이 의도된 정해이다. 스택의 push(), pop() 연산은 모두 시간복잡도가

O_{(1)}

이기 때문에, 이렇게 풀면 시간 초과 오류가 나지 않는다.

3. 정답 코드 [편집]

3.1. Javascript [편집]

코드 보기/접기

const fs = require('node:fs');

let [orig, explode] = fs.readFileSync(0, 'utf-8').split('\n');
const stack = [];
const exLen = explode.length;

for (let i = 0; i < orig.length; i++) {
  stack.push(orig[i]);
  if (stack.slice(-exLen).join('') === explode) {
    for (let i = 0; i < exLen; i++) {
      stack.pop();
    }
  }
}

console.log(stack.join('') || 'FRULA');