문자열 폭발

문제

언어

  • JavaScript

순서도

  1. 간단한 스택 구현 또는 배열 사용
  2. 주어진 문자열에 대해서 한 글자씩 검사
    1. 검사 도중 문자열의 글자가 폭탄 문자열의 마지막 글자와 같다면 폭탄 문자열 검사
    2. 폭탄 문자열이 존재하면, 폭탄 문자열 제거
    3. 폭탄 문자열이 아니라면 다시 스택에 넣고, 검사 진행
    4. 주어진 문자열의 끝에 도달할 때까지 위 과정 반복
  3. 검사 과정이 끝나고 스택이 비어있다면, “FRULA” 출력
  4. 스택이 비어있지 않다면, 스택에 들어있는 문자열을 순서에 맞게 배치 후 출력

문제 풀이 step 1

  • 문자열 안에 폭발 문자열이 있는데, 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 됩니다.
  • 폭발은 다음과 같은 과정을 진행됩니다.
    • 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 됩니다.
    • 폭발 후 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만듭니다.
    • 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있습니다.
    • 폭발은 폭발 문자열이 문자열에 없을 때까지 계속 됩니다.

문제 풀이 step 2

  • 우선, 문자열의 각 문자를 하나씩 검사하며, 마지막 문자에 도달할 때 까지 반복문을 진행합니다.
    • 우선, 스택에 글자를 push 합니다.
    • 스택의 맨 위의 글자가 폭탄 문자열의 마지막 문자와 같다면, 폭탄 문자열 검사를 진행합니다.
      • 폭탄 문자열 검사는
      • 임시 스택을 하나 생성한 다음에, 현재 스택에서 한 글자씩 pop 해서 임시 스택에 넣어줍니다.
      • 이와 동시에 스택에서 pop 한 글자가 폭탄 문자열과 일치하는 지 비교합니다. 이 때, 검사는 폭탄 문자열의 역순으로 진행됩니다.
      • 검사 도중 폭탄 문자열과 모두 일치하다면, 폭탄 문자열을 제거하고,
      • 일치하지 않다면, 임시 스택에서 다시 pop 을 하며 원래 스택에 다시 넣어줍니다.
  • 반복문이 종료되면, 스택에 남아 있는 문자들을 정제해서 출력합니다.
    • 만약 스택에 남아 있는 문자가 하나도 없다면 “FRULA” 를 출력합니다.
    • 만약 스택에 문자가 남아있다면, 스택에서 pop 하고 다시 순서대로 변환 후 출력하면 정답입니다.
  • 추가 설명은 주석으로 작성하겠습니다.

후기

  • 꼭 다시 풀어볼 문제입니다.
  • 문자열을 처음부터 한 글자씩 스택에 넣어가면서 앞에서부터 폭발 문자열을 찾는 방법만 계속 생각하느라 쉽게 풀 수 없었습니다.
  • 생각의 전환을 해서 문자열의 앞에서부터 폭발 문자열을 찾는 것이 아니라 폭발 문자열의 마지막 글자만 비교함으로써 쉽게 풀 수 있었습니다.
  • 폭발 문자열의 마지막 글자를 비교하게 되면,
    • 비교 당시, 어차피 스택에 폭발 문자열이 다 들어간 상태이기 떄문에 비교하기가 쉽습니다.
    • 폭발 문자열이 중첩되는 경우에도 중첩된 문자열의 내부에서부터 차례대로 비교가 가능합니다.
  • 문자열을 앞에서부터 하나씩 비교하는 것이 아닌, 문자열의 마지막만 비교하는 생각의 전환이 중요했던 좋은 문제입니다.

소스 코드

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

// 간단한 스택 구현
// 필요한 메서드 생성해서 사용
class Stack {
	constructor() {
		this.bucket = [];
		this.top = -1;
	}

	push(data) {
		this.bucket[++this.top] = data;
	}

	pop() {
		return this.bucket[this.top--];
	}

	peek() {
		return this.bucket[this.top];
	}

	isEmpty() {
		return this.top === -1;
	}

	size() {
		return this.top + 1;
	}
}

// 폭발 문자열인지 검사 후 제거
const deleteBomb = (stack, bomb) => {
	const tempStack = new Stack();

	// 스택에서 한 글자씩 빼가면서, 폭발 문자열과 일치하는 지 검사
	let isExist = true;
	for (let i = bomb.length - 1; i >= 0; i--) {
		tempStack.push(stack.pop());

		if (tempStack.peek() !== bomb[i]) {
			isExist = false;
			break;
		}
	}

	// 폭발 문자열과 일치하지 않다면, 다시 원래 스택에 넣어주기
	if (!isExist) {
		while (!tempStack.isEmpty()) {
			stack.push(tempStack.pop());
		}
	}
};

const solution = (input) => {
	let str = input[0].split("");
	const bomb = input[1];
	bombLast = bomb[bomb.length - 1];

	const stack = new Stack();
	for (let i = 0; i < str.length; i++) {
		stack.push(str[i]);

		// 문자열의 글자가 폭탄 문자열의 마지막 글자와 같다면, 폭탄 문자열인지 검사
		if (stack.peek() === bombLast) deleteBomb(stack, bomb);
	}

	// 위의 반복이 끝난 후에 스택이 비어있으면, "FRULA" 출력
	if (stack.size() === 0) return "FRULA";

	// 스택에 문자가 남아 있으면, 다시 문자열을 순서대로 만든 후에 출력
	const result = [];
	for (let i = stack.size() - 1; i >= 0; i--) {
		result[i] = stack.pop();
	}

	return result.join("");
};

console.log(solution(input));