백준 9935 - 문자열 폭발

접근

실패한 접근 : replace를 통해서 계속 돌려보기 - 계속해서 새로운 string을 만드는 구조라 효율적이지 못함.

반복적으로 새로운 문자열을 생성하는 구조 : 시간 초과

정답 접근 스택을 활용하자.

입력 문자열을 한 글자씩 스택에 넣음
스택의 마지막 부분이 폭발 문자열과 일치하는지 확인
일치하면 해당 부분을 pop
연쇄작용도 간단히 해결됨

코드

Java

StringBuilder를 스택처럼 활용해서 해결.

찾아보니 해당 요소는 가변적이라 함. (이득)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException{
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

      String str = br.readLine();
      String exp = br.readLine();
      br.close();

      StringBuilder res = new StringBuilder();
      int expLength = exp.length();

      for (int i = 0 ; i < str.length(); i++  ) {
        char curChar = str.charAt(i);

        res.append(curChar);

        if (res.length() >= expLength) {
          boolean match = true;
          for (int j = 0; j < expLength; j++) {
            if (res.charAt(res.length() - expLength + j) != exp.charAt(j)) {
              match = false;
              break;
            }
          }
          if (match) {
            res.setLength(res.length() - expLength);
          }
        }
      }

      if (res.length() == 0 ) {
        System.out.println("FRULA");
      } else {
        System.out.println(res);
      }
    }
}

Node.js

자바와 비슷한 접근 방식.

다만 효율적으로 문자열을 다루기 위해 배열을 스택처럼 사용하고 마지막에 join('')을 통해 해결.

splice와 split의 차이에 대해 자세히 공부할 필요성을 느낌.

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

const originalStr = input[0];
const explosionStr = input[1];
const expLen = explosionStr.length;

const resultArr = [];

for (let i = 0; i < originalStr.length; i++) {
  const currentChar = originalStr[i];

  resultArr.push(currentChar);

  if (resultArr.length >= expLen) {
    let match = true;
    for (let j = 0; j < expLen; j++) {
      if (resultArr[resultArr.length - expLen + j] !== explosionStr[j]) {
        match = false;
        break;
      }
    }

    if (match) {
      resultArr.splice(resultArr.length - expLen, expLen);
    }
  }
}

if (resultArr.length === 0) {
  console.log("FRULA");
} else {
  console.log(resultArr.join(""));
}

여담

FRULA 는 악기의 이름이라고 한다.

정답이 비어있는 경우 Frula 를 출력하는 이유는

string (문자열, 현) - 아무것도 남지 않으면 (string이 없다면) 관악기라는 말장난이라고 한다.

하하… 하하하…

와중에 첫 예제 입력인

mirkovC4nizCC44
C4

여기도 C4. 하필 폭약이다. 여러 의미로 재밌게 푼 문제.

[Java & Node.js] 백준 9935 - 문자열 폭발

나쁘지 않은데?

백준 9935 - 문자열 폭발

접근

코드

Java

Node.js

여담