[자료구조] 01 배열과 문자열
2016. 6. 8. 22:26 - Daybreak0_0
StringBuffer
아래의 코드의 실행 시간은? 문자열 길이는 x로 똑같고, 문자열 개수는 n이라고 하자.
1 2 3 4 5 6 7 | public String joinWord (String[] words) { String sentence = ""; for(String w : words ){ sentence = sentence + w; } return sentence; } | cs |
문자열을 연결할 때마다 새로운 문자열 객체가 만들어지고, 연결할 문자열의 값이 문자 단위로 복사된다.
So, 첫 루프에서는 x개의 문자가 복사될 것이고, 두번째 루프에서는 2x개, 세번째 루프에서는 3x 문자열이 복사된다.
결국 소요되는 시간은 O( x + 2x+ 3x + ... + nx ) 즉, O ( xn^2 ).
StringBuffer는 모든 문자열의 배열을 만들어두고, 문자열 객체로의 복사는 필요할 때만 수행한다.
1 2 3 4 5 6 7 8 | public String joinWord2 (String[] words) { StringBuffer sentence = new StringBuffer(); for (String w : words) { sentence.append(w); } return sentence.toString(); } | cs |
예제
같은 문자가 연속으로 반복되는 경우, 그 획수를 사용해 문자열을 압축하는 메서드 구현하기
예를들면, aabccccccccaaa라면 a2b1c8a3 과 같이 나오도록 !