Java String클래스의 replaceAll() 메소드의 작동 방식?

Question

제목 그대로 replaceAll() 메소드의 작동 방식이 궁금합니다.검색해도 관련 정보를 찾을 수 없어 질문드립니다. 제가 생각하기에는 replaceAll('abc', 'def')를 호출했을 때 모든 문자열을 검색하면서 abc -> def로 치환하는 것 같습니다. 대충 생각하면 시간 복잡도가 O(n)이라고 생각했었는데요. 다시 한 번 생각해보니.. 위 메소드를 통해 zxabhabc라는 문자열을 zxabhdef로 바꾸려면 O(n^2)이라고 생각합니다. 아래와 같이 연속된 문자열을 찾기 위해 하나의 글자에서 그 다음글자까지 계속 파고들어가야 하기 때문입니다.z->실패 x->실패 a->b->h->실패 b->실패 ... a->b->c->성공->변환 실제 String클래스의 Replace 메소드도 이러한 방식으로 되어있는지 알고 싶은데 소스 코드를 못 찾겠습니다..ㅠ혹시 코드를 아신다면 링크 좀 걸어주시거나 아니면 개념적인 부분이라도 간단하게 설명해주시면 감사하겠습니다..ㅠ

돈까스 · Accepted Answer

문자열 검색에 대한 효율적인 알고리즘들이 있습니다. 생각하신 n^2 방식을 개선한 것들이 있고, 어떤 아이디어로 그렇게 되는지는 검색해보세요.https://www.google.co.kr/search?q&#61;문자열&#43;검색&#43;알고리즘&ie&#61;UTF-8&oe&#61;UTF-8&hl&#61;ko-kr&client&#61;safari 이클립스를 잘 설치하셨다면 보통은 소스코드 탐색 기능으로 호출된 메소드를 그냥 따라가기만 하도 Java 기본 라이브러리 소스들을 볼 수 있습니다. 안되면 검색해서 해보세요.https://www.google.co.kr/search?client&#61;safari&hl&#61;ko-kr&ei&#61;3sT0WsfQNomr8QX89ZzwBw&q&#61;이클립스&#43;자바&#43;소스코드&#43;보기&oq&#61;이클립스&#43;자바&#43;소스코드&#43;보기

load2000 · Answer

java.lang.String class public String replaceAll(String regex, String replacement) { return Pattern.compile(regex).matcher(this).replaceAll(replacement); }

짜언이 · Answer

&#64;load2000 감사합니다. 막상 소스코드봐도 이해가 잘 안되네요 크..&#64;돈까스 아 문자열 검색 알고리즘을 검색해볼 생각을 못했네요. 감사드립니다

Java String클래스의 replaceAll() 메소드의 작동 방식?

3개의 답변

Q&A 목록