[LeetCode/Java]Array and String - Immutable String : Problems & Solutions

나중에 다시 찾아보기 위한 한글 번역 및 요약

 

Java의 경우 문자열의 중간을 변경하지 못하는 문제와 문자열 추가 시 시간이 오래 걸리는 문제가 있습니다.

이 문제에 대한 해결책입니다.

 

1. 문자열 수정 작업

 

문자열을 수정하기 위해서는 문자 배열(char[])을 이용하여 수정할 수 있습니다.

public class Main {
    public static void main(String[] args) {
        String s = "Hello World";
        char[] str = s.toCharArray();
        str[5] = ',';
        System.out.println(str);
    }
}

 

2. 문자열 추가 작업

public class Main {
    public static void main(String[] args) {
        String s = "";
        int n = 10000;
        for (int i = 0; i < n; i++) {
            s += "hello";
        }
    }
}

위와 같이 for문으로 문자열을 추가 할 때 시간 복잡도는 다음과 같습니다.

   5 + 5 × 2 + 5 × 3 + … + 5 × n
= 5 × (1 + 2 + 3 + … + n)
= 5 × n × (n + 1) / 2

 

이것은 

과 같습니다.

 

이것에 대한 해결법은 StringBuilder와 같은 다른 데이터 구조를 사용하는 것입니다.

 

public class Main {
    public static void main(String[] args) {
        int n = 10000;
        StringBuilder str = new StringBuilder();
        for (int i = 0; i < n; i++) {
            str.append("hello");
        }
        String s = str.toString();
    }
}

StringBuilder를 사용하면 코드 복잡도는 O(n)이 됩니다.