백준 9935번 문자열 폭발
https://www.acmicpc.net/problem/9935
시도 1 (메모리 초과)
contains, replaceAll 메소드를 사용해보았다
Java String 클래스에는 contains, replaceAll 등의 유용한 메소드들이 구현되어있다.
이런 메소드에 익숙하다면, contains로 폭발 문자열이 있는 지 체크한 후 replaceAll을 적용하는 방식을 떠올리기 쉬울 것이다.
나 역시도 초기엔 이런 방식으로 시도하였고, 결과는 메모리 초과.
우선 replaceAll에서 정규식 표현을 위해 사용하는 Pattern 인스턴스가 불필요하게 반복적으로 생성된다.
다만 Pattern 객체를 미리 생성해두고, 이를 사용하도록 처리해도 메모리 초과가 뜨는 것으로 보아 잦은 변경으로 인해 신규 생성된 String 객체 역시 문제가 되리라 생각했다.
시도 2 (성공)
Stack을 사용해보자
input값을 character 단위로 쪼개 하나씩 Stack에 쌓아보자.
Stack의 사이즈가 폭발 문자열보다 크거나 같고, top에 있는 문자가 폭발 문자열의 마지막 문자와 같을 때 폭발 문자열의 길이만큼 비교를 수행한다.
일치한다면 폭발하고, 그렇지 않다면 다시 Stack을 쌓는다.
다만, Stack 객체를 생성해 쓰는만큼 메모리를 적잖이 사용하는 것을 볼 수 있다.
그리고 output을 만들기 위해 Stack의 element들을 하나씩 읽어야 하는 번거로움이 있다.
성능 개선을 위해 Stack 대신 Array를 사용해보자.
