백준 5분 읽기

문자열 폭발

문제를 요약하자면 기준 문자열과 폭발 문자열을 입력받고, 기준 문자열에서 폭발 문자열을 제거한 새로운 문자열을 만들고 거기서 폭발 문자열을 다시 제거하고를 반복해서 최종적으로 나오는 문자열을 출력한다.

백준알고리즘

백준 문자열 폭발

문제 링크 : https://www.acmicpc.net/problem/9935

문제

문제를 요약하자면 기준 문자열과 폭발 문자열을 입력받고, 기준 문자열에서 폭발 문자열을 제거한 새로운 문자열을 만들고 거기서 폭발 문자열을 다시 제거하고를 반복해서 최종적으로 나오는 문자열을 출력한다.

만약, 남은 문자가 없으면 FRULA를 출력한다.

접근 방식

제일 먼저 떠오른 방법은 당연히 재귀였다. 문자열에서 해당 문자를 제거하고 제거된 문자열을 다시 확인하는 방식이니까 하지만, 문자열의 최대 길이가 1,000,000이기 때문에 콜스택에 문제가 생길 것이라는 생각에 구현은 따로 하지 않았다.

다음으로 떠올린 방법은 스택이다. 실제로 이 문제의 알고리즘 분류 역시 스택이다. 스택을 이용해 스택에 PUSH를 할 때마다 폭발 문자열이 만들어졌는지 확인하고 그렇다면 해당 문자들을 POP하는 방법이다. 방식이 쉬우니 구현도 어렵진 않다.

구현

자바스크립트를 이용해서 구현했다.

먼저 문자를 넣을 스택을 만든다. 자바스크립트의 array는 스택처럼 사용할 수 있다. 심지어 메소드도 push, pop이 있기 때문에 스택으로 사용이 가능하다.

const s = [];

다음으로 새로운 문자가 들어왔을 때 스택에 쌓이면서 폭발 문자열이 만들어졌는지 확인하는 함수를 만든다. 만약 이 함수의 결과가 true라면 폭발 문자열 길이만큼 pop해줄 것이다.


function checkIsBomb(ar, b) {
  return ar.slice(ar.length - b.length, ar.length).join("") === b;
}

스택에 문자를 넣으면서 위 함수를 이용해서 폭발 문자열이 만들어졌는지 확인하고 pop을 한다. pop을 한 뒤에는 새로운 문자가 들어왔을 때 또 폭발 문자열이 만들어졌는지 비교하기 때문에 폭발 문자열을 제거한 뒤에 다음 문자가 들어오면서 다시 폭발 문자열이 만들어져도 판별이 가능하다. 판별하는 방법이 위의 함수와 같기 때문이다.

for (const a of str) {
  s.push(a);
  if (checkIsBomb(s, c4)) {
    for (let i = 0; i < c4.length; i++) s.pop();
  }
}

최종적으로 스택에 문자가 남아있는지 확인해 결과를 출력한다.

if(s.length) console.log(s.join(''));
else console.log('FRULA')

전체 코드

let fs = require('fs')
let input = fs.readFileSync('dev/stdin').toString().split('\n')

const [str, c4] = input;
const s = [];

for (const a of str) {
  s.push(a);
  if (checkIsBomb(s, c4)) {
    for (let i = 0; i < c4.length; i++) s.pop();
  }
}
if(s.length) console.log(s.join(''));
else console.log('FRULA')

function checkIsBomb(ar, b) {
  return ar.slice(ar.length - b.length, ar.length).join("") === b;
}

리뷰

문제 자체는 어렵지 않은 내용이었고, 이해가 쉬웠다. 구현 방법도 바로 떠올라서 어렵지 않았지만, 조금 더 효율적인 방법이 없나 고민하던 중 pop을 반복하면서 하지말고 slice를 이용해서 앞에서부터 폭발 문자열을 제거한 위치까지 자르는 방식을 써봤는데 메모리 초과가 되길래 일단 구현을 멈췄다.

checkIsBomb함수를 조금 더 좋은 형태로 짤 수 있을 것 같다는 생각이 든다. 예를 들면 sliceFromBack이라는 함수를 만들어 뒤에서 부터 원하는 길이만큼 잘라 새로운 배열을 반환하는 함수를 만들고 그 함수를 checkIsBomb에서 사용하는 방식?

그래서 구현해봤다.

function sliceFromBack(ar, b){
    return ar.slice(ar.length - b.length, ar.length);
}

function checkIsBomb(ar, b) {
  return sliceFromBack(ar,b).join("") === b;
}

join메소드를 쓰는 게 마음에 들진 않지만 나쁘진 않은 것 같기도 하다.