시간 초과가 나는 건 당연한 거에요.

쭉 돌면서, 제거한 문자열이 없는 경우, break를 걸어서 빠져 나오겠다는 것인데요.

split가 내부적으로 어떻게 구현이 되어 있는지는 잘 모르겠지만.. 상식적으로 생각해 보면요.

분리할 문자열이 있나. 그걸 계속 탐색한 다음에, 분리할 문자열이 있으면 분리! 하고 분리된 위치 다음부터 탐색해야 하지 않을까요?

sub string을 찾는 알고리즘을 계속 수행해야 겠죠. KMP 같은 알고리즘을 쓰지 않는 이상 O(nm)이 걸리고요.

근데 split는 정규식까지 받는단 말이죠.

원 문자열이 abababababababab이고, abababaa를 기준으로 분리하겠다. 그러면.. 조금 더 최악일 수도 있겠군요.

아무튼. 시간 복잡도는 O(nm)이겠군요. 그런데, 이게 끝이 아닌 게 더 문제겠죠. 남은 문자열에 대해서 또 지우기를 하셔야 할 거고요.

그러면 대충 O(n*n*m) 쯤 되지 않을까요? 정확하진 않겠지만, 확실한 건 별로 효율적이지 않다는 것 정도 되겠죠.

KMP를 쓴다면 m 하나가 지워지겠지만 여전히 O(n^2)고요.

거기에다가, String을 결합하는데 + 연산자를 쓰셨군요. String은 불변 객체로 알려져 있습니다.

(실제로는 char형 배열이 final로 선언되어 있죠..)

문자열 추가를 할 때, 어떤 연산이 이루어 지냐면요. StringBuffer로 변환을 시킨 다음에, append를 시킵니다. 그리고 요걸 또 String으로 변환시키겠군요?

중간에 생성된 StringBuffer는 사실상 필요 없는 겁니다. 이게 그대로 가비지로 가지 않을까요?

결론부터 말씀드린다면. 네! 스택을 쓰시면 됩니다만..

일단 java의 문자열 처리 클래스에 대해서 다시 한 번 보시는 게 어떨까 싶습니다. String, StringBuffer, Builder 이것들은

많은 분들이 커뮤니티에 성능 관련해서 물어보시는 주제 중에 하나라서요. 정확하게 알고 넘어가실 필요가 있습니다.

구글링 해 보셔도 좋지만

내부 코드를 보시면서 분석하시는 게 더 좋으실 듯 싶습니다. 그러면서 종이에 메모리가 어떻게 할당되고, 가비지가 어떻게 생기는지. 

꼭 디버깅 해 보시면서 그려보세요. 그러면 동적 배열에 대해서도 아실 수 있을 것입니다.

동적 배열이라고 해 봤자 별 거 없습니다.

확장할 수 있다는 차이만 있는데요. 크기가 10인 것을 15로 확장한다고 가정하면, 15짜리를 먼저 할당하고

10짜리에 있는 걸 15짜리에 복사한 후에, 10짜리를 가비지로 만들어 버리지요. (어짜피 쓸모없는 공간이니까요.)

중간 중간에 grow rate에 대해서 나오게 될 텐데.

이에 대해서는 제가 따로 설명드리지 않겠습니다. 공부하다보면 자연스레 알 것 같기 때문입니다.

아.. 답변보고 많은 생각이 드네요.

지금까지 한 공부가 겉핥기 식 공부인 것 같아서.. 다시 제대로 공부해보도록 하겠습니다.

감사합니다.