StringBuilder 초기화하는 방법
- new로 인스턴스 새로 생성
StringBuilder sb = new StringBuilder();
for (int i=0; i<1000000000; i++) {
sb = new StringBuilder();
}
10억회 반복 시 속도 -> 64ms
2. delete() 메서드 사용
StringBuilder sb = new StringBuilder();
for (int i=0; i<1000000000; i++) {
sb.delete(0, sb.length());
}
10억회 반복 시 속도 -> 4ms
3. setLengt() 메서드 사용
StringBuilder sb = new StringBuilder();
for (int i=0; i<1000000000; i++) {
sb = new StringBuilder();
}
10억회 반복 시 속도 -> 4ms
매번 new를 이용해 객체를 새로 생성해 초기화하는 방법은 실행속도 측면에서 가장 최악이었다.
나머지 방법과 비교해 무려 16배 가량 느린 속도를 보여줬다.
그리고 setLength, delete 메서드를 사용해 초기화 하는 방법은 4ms로 비슷한 모습을 보였다.
앞으로 StringBuilder를 초기화해야 할 경우엔 객체 생성은 최대한 피해야 하겠다.
나의 경우에는 delete보단 setLength 메서드가 더 사용하기 간편하기에 setLength를 사용할 것 같다.
실제 알고리즘 문제에 적용 시 속도는 ?
그렇다면 실제 문제에 적용하면 어떨까?
백준 문제 내용은 아래 링크 참조.
백준 10666: N과M(12)
내 제출 코드
조합(Combination) 알고리즘을 사용해 수열에서 필요한 개수만큼 숫자를 뽑은 후,
중복되는 수열을 제거하는 과정에 StringBuilder를 사용했다.
(물론 효율적인 방법이 아니기에 개선 필요.)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
/*
* 비내림차순이어야 하므로, 배열 입력받은 후 정렬하고 조합 작업 시작해야 함.
* 배열을 오름차순으로 정렬하고, 0번 인덱스부터 선택할지 안할지 탐색.
* 최종 수열 완성 시 이미 존재하는지 여부 확인.
*
* 시간복잡도 개선을 위해 배열로 관리.
*/
public class Main {
static int N, M;
static int[] arr;
static int[] tmp;
static String[] pick;
static int size;
static StringBuilder sb;
static StringBuilder ans;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
sb = new StringBuilder();
ans = new StringBuilder();
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
arr = new int[N]; // 원본 배열
tmp = new int[M]; // 숫자 조합 배열
pick = new String[6435]; // 최종 출력할 조합 (최대크기인 8C4 = 70)
size = 0; // 최종 출력할 조합 배열의 크기
// 배열 입력
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
arr[i] = Integer.parseInt(st.nextToken());
}
Arrays.sort(arr); // 배열 오름차순 정렬
combination(0, 0); // 조합 시작
System.out.println(ans);
}
private static void combination(int aidx, int tidx) {
// 기저조건: tidx가 M에 도달했을 때
if (tidx == M) {
for (int n : tmp) {
sb.append(n).append(' '); // 공백을 추가해서 숫자를 구분
}
// 중복 여부 확인
for (int i = 0; i < size; i++) {
if (pick[i].equals(sb.toString())) {
sb.setLength(0);
return;
}
}
// 중복 없다면 arr배열에 추가 후 정답 출력
pick[size++] = sb.toString();
ans.append(sb).append('\n');
sb.setLength(0);
return;
}
// 불완전 선택 (무시): aidx가 N 이상이면 더 이상 선택할 수 없음
if (aidx >= N) {
return;
}
// 재귀 호출부
for (int i = aidx; i < N; i++) {
tmp[tidx] = arr[i]; // tidx는 M을 넘지 않음
combination(i, tidx + 1); // i를 그대로 넘기므로 중복 조합 허용
}
}
}
여기에서 StringBuilder를 초기화하는 부분만 3가지 방법 각각으로 수정해 비교해보겠다.
???????????????????
setLength가 가장 짧지만 유의미한 차이는 아니였다...
그러니 참고만 하자.