StringBuilder, String compression(문자열 압축)

1st approach

logic

처음 드는 생각

//Sudo code
ns = ""
c = 0
for(i < s.len){
	c++
	if(s.get(i) != s.get(i+1)){
		ns = ns + s.get(i)+c
		c = 0
	}
}

결과를 저장할 문자열 선언 문자열 개수를 위한 정수 선언

주어진 문자를 한 자씩 돌면서 문자가 다음 문자와 다른지 비교

• 다를 경우 count를 해당 문자와 결과 문자에 붙인다

문제점

마지막 문자에서 Null Exception에러가 발생한다 Q) 문자열의 맨 마지막 한글자는 어떻게 처리해야 할까?

2nd approach

마지막 문자 고려

• 마지막 문자가 그 전의 문자와 다르다면 count가 0으로 세팅 되어있을 테니 count를 1개 늘리고 자기 자신을 출력해주면 된다
• 마지막 문자가 그 전의 반복되는 문자라면 count하나 늘려서 그대로 출력

  //Sudo code
  ns = ""
  c = 0
  for(i < s.len){
    c++
    if(i + 1 > s.len || s.get(i) != s.get(i+1)){
        ns = ns + s.get(i)+c
        c = 0
    }
  }
  

• i + 1 > s.len - 마지막 문자일때의 조건

문제점

• 문자열을 고치는 부분이 문제
• 단순해 보이지만 String을 붙이는 부분이 비효율 적이다
  • 기존의 문자열 개수, 새로 추가되는 문자열의 개수 합산 후 새로운 문자열 생성 후 내부의 문자열을 하나씩 복사
  • 위를 loop 돌때 마다 반복.. 처리 속도가 느려진다

3rd approach

StringBuilder

• 문자를 +기호로 concate하는것 보다 훨씬 속도가 빠르다

//Sudo code
StringBuilder ns = new StringBuilder();
c = 0
for(i < s.len){
	c++
	if(i + 1 > s.len || s.get(i) != s.get(i+1)){
		ns.append(s.get(i))
		ns.append(c)
		c = 0
	}
}

문제점

• StringBuilder도 문자열이 어느정도 차면 공간을 늘려주기 위해서 새로운 배열을 생성하고 문자들을 한자한자 죄다 복사하는 작업을 뒤에서 처리한다

Q) 이런 작업을 없애기 위해서 우리가 새로 들어갈 문자열의 길이를 미리 알면 처음에 StringBuilder선언시 생성자에 크기를 넘겨주고 고정된 크기의 공간을 만들어 주면 되지 않을까? 그러면 중간에 공백을 늘릴 필요도 없으니까!

압축한 결과의 문자열의 길이는

• 문자열을 돌면서 반복되는 문자의 개수를 세고
• 결과 문자열에 붙여줘야 할 문자 대신에 붙여줄 문자의 개수를 total값에 더해준다

코드 구현

class Test {
	public static void main(String[] args) {
		System.out.println(compressString("aabbbbbccccdd"));
		System.out.println(compressString("abcd"));
	
	}
	private static String compressString(String str) {
		String newStr = compress(str);
		// 두 개중에 짧은 것을 반환
		return str.length() < newStr.length() ? str : newStr;  
	}

	private static String compress(String str) {
		int count = 0;
		StringBuilder newString = new StringBuilder(getTotal(str));
		for(int i = 0; i < str.length(); i++){
			count++;
			if(i+1 >= str.length() || str.charAt(i) != str.charAt(i+1)) {
				newString.append(str.charAt(i));
				newString.append(count);
				count = 0;
			}
		}
		return newString.toString();
	}

	// 결과로 반환할 문자열이 몇개가 될지 미리 getTotal함수를 통해 획득
	private static int getTotal(String str) {
		int count = 0;
		int total = 0;
		for(int i=0; i<str.length(); i++) {
			count++;
			if(i+1 >= str.length() || str.charAt(i) != str.charAt(i+1)) {
				total += 1 + String.valueOf(count).length();
				count = 0;
			}
		}
		return total;
	}
}

출력로그

a2b5c4d2
abcd

---

• github - string compression