String.split("") 효율성 테스트

프로그래머스의 올바른 괄호라는 문제를 풀던 도중 아래 코드 중 split을 사용하는 코드가 효율성 테스트에서 막히는 것을 발견했습니다. 알고리즘 상으로는 문자열의 길이 n만큼 탐색하는 O(n)인데 시간초과가 나길래 문자열의 길이에 따라 split()의 시간이 얼마나 차이 나는지 테스트 해봤습니다.

String[] tokens = s.split("");
for(String token: tokens){
    if(token.equals("("))
        stack.push(token);
    else
    {
        if (!stack.empty())
            stack.pop();                    
    }
}

 

for (int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if (c == '(') {
        stack.push(c);
    } else {
        if (!stack.isEmpty())
            stack.pop();
    }

}

문자열의 길이가 3000만 일 때 기준으로 split()의 실행시간은 3.4초이고 그 이후는 outOfMemory가 뜨는 것을 확인했습니다.

 

이렇게까지 극단적인 경우는 보통 없겠지만 효율성이 중요한 알고리즘 문제를 풀 때는 charAt()을 통해 접근하는 것이 좋을 것 같습니다.