[백준/JAVA] 9935번 문자열 폭발

문제 보러가기

9935번: 문자열 폭발

[코드]

import java.io.*; import java.util.*; class Main {     public static void main(String[] args) throws IOException {         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));         char[] strings = br.readLine().toCharArray();         char[] exp = br.readLine().toCharArray();         StringBuilder sb = new StringBuilder();         /*             알고리즘             1. StringBuilder에 문자를 차례대로 넣어준다.             2. StringBuilder 길이가 폭발문자열의 길이와 같거나 큰지 확인한다.             3. 만약 크다면 StringBuilder의 맨끝에서부터 폭발문자와 같은지 확인한다.             4. 만약 같다면 해당 문자열을 삭제한다.          */         for (int i = 0; i < strings.length; i++) {             sb.append(strings[i]); //문자를 차례대로 넣어준다.             if (sb.length() >= exp.length) { //폭발문자열의 길이와 비교한다.                 boolean check = true; // 만약 false가 되면 폭발문자열과 불일치한다.                 for (int j = 0; j < exp.length; j++) {                     char ch = exp[j];                     char sc = sb.charAt(sb.length() - exp.length + j); //문자열 끝에서부터 확인한다.                     if (ch != sc) {                         check = false;                         break;                     }                 }                 if (check) sb.delete(sb.length() - exp.length, sb.length()); //폭발문자열과 같다면 해당 문자열을 삭제한다.             }         }         if (sb.length() == 0) bw.write("FRULA");         else bw.write(sb.toString());         bw.close();     } }

[문제풀이]

처음 문제를 보고 String.replace()을 활용하여 풀었는데 메모리초과가 나왔다. 그 이유는 String은 불변이면서 참조타입이기 때문에 Heap영역에 데이터를 저장하는데 String.replace()를 할 때마다 새로운 String을 할당하기 때문이다.

그렇기 때문에 가변 속성을 가진 StringBuilder나 스택을 사용하여 문제를 풀어야한다.