잠깐만요
String 클래스의 replace() 메서드에 해당하는 시간 복잡도가 어떻게 O(N)일까요? 변환하려면 문자열을 원본 문자열에서 찾아야 하는데, 찾는 문자열의 길이가 시간 복잡도에 영향을 미치지 않았을까요? 그렇습니다. 놀랍게도 찾는 문자열의 길이는 문자열 검색에서 중요하지 않습니다.
이는 문자열 검색 알고리즘 중 KMP(Knuth Morris Partt) 알고리즘을 살펴보면 이해할 수 있는데요. 이 알고리즘은 원본 문자열의 길이를 N, 찾는 문자열의 길이를 M이라고 했을 때 O(N+M)의 시간 복잡도를 갖습니다. 찾는 문자열의 길이가 원본 문자열의 길이보다 크다면 애초에 검색할 수 없는 문자열이기 때문에 둘 중 더 큰 값인 O(N)으로 표기할 수 있습니다.
전체 코드
4장/숫자_문자열과_영단어.java
public class Solution {
private static final String[] words = {
"zero", "one", "two", "three", "four",
"five", "six", "seven", "eight", "nine",
};
public int solution(String s) {
for (int i = 0; i < words.length; i++) {
s = s.replace(words[i], Integer.toString(i));
}
return Integer.parseInt(s);
}
}