[JAVA] 문자열 압축

문제

https://programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

내 풀이

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = s.length();
        int maxLength = s.length() / 2;
        for (int i=1; i<=maxLength; i++) {
            answer = Math.min(answer, getZippedSize(s, i));
        }
        return answer;
    }
    
    private int getZippedSize(String s, int div) {
        StringBuilder zipped = new StringBuilder();
        String target = "";
        int slice = s.length() % div;
        String zipping = s.substring(0, s.length() - slice);
        int outer = 0;
        int targetCount = 1;
        
        
        while(outer < zipping.length()) {
            target = s.substring(outer, outer + div);
            targetCount = 1;
            for(int inner= outer+div; inner < zipping.length(); inner += div) {
                if (target.equals(s.substring(inner, inner+div))) {
                    targetCount++;
                } else {
                    zipped.append(this.addZippedSubString(target, targetCount));
                    break;
                }
            }
            outer += (div * targetCount);
        }
        zipped.append(this.addZippedSubString(target, targetCount));

        return zipped.toString().length() + slice;
    }
    
    private String addZippedSubString(String target, int targetCount) {
        StringBuilder compression = new StringBuilder();
        if (targetCount == 1) {
            compression.append(target);
        } else {
            compression.append(targetCount);
            compression.append(target);
        }
        return compression.toString();
    }
}

 

1. 받은 문자열이 압축될 수 있는 최대 크기는 문자열의 절반이다. (abcabc의 경우 abc / abc 가 가능한 최대 압축 단위 길이이다)

2. 압축단위 길이 1 ~ maxLength 까지 압축을 진행하며 압축된 길이의 최소값을 비교한다.

3. 문자열길이가 압축단위길이의 배수가 아닌 경우, 나머지 문자열을 뒤에서부터 잘라서 더한다. (abcabcd 일때 압축길이가 3이면 d를 떼어낸다)

4. 최소일 때의 문자열 길이를 리턴한다.

 

알게 된 것

재귀로 풀면 코드량이 굉장히 짧아진다

피드백

엣지 케이스를 테스트 케이스로 삽입해 돌려보도록 하자

엣지 케이스란? 극단적인 작동 매개변수에서만 발생하는 문제 또는 상황

계속 1개의 케이스에서만 실패가 났는데, 조건문이 문제가 있나해서 계속 고쳤는데 알고보니 input이 1일때를 고려하지못해서 틀린 것 이었다.

 

StringBuilder 를 사용하는게 좋겠다. 처음에는 String을 단순히 concatenate하는 방식으로 문자열을 이어붙이다보니 실행시간이 많이 차이가 나게되었다.

왼쪽이 String 덧셈으로 진행, 오른쪽은 StringBuilder로 append

차이가 유의미하게 발생한다. str = str1 + str2 는 새로운 객체를 무조건적으로 생성하기 때문에 메모리 할당과 해제에 있어 연산작업이 훨씬 많이 요구된다. 멀티스레드 환경에서는 동기화가 보장되는 StringBuffer를 사용하자.