[2020 KAKAO BLIND RECRUITMENT] 문자열 압축 (JAVA)

 

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

 

 

public class 문자열압축 {
    public static int solution(String s) {
        int answer = Integer.MAX_VALUE;
        
        // 입력 받은 문자열의 길이가 1이면 1을 리턴
        if (s.length() == 1)
            return 1;
        
        // 문자열의 최대 압축 길이는 절반까지 가능하다.
        // ex. aabbaa (최대 압축 단위는 3)
        // 4개 단위로 압축하면? aabbaa => 6
        // 5개 단위로 압축하면? aabbaa => 6
        int max_len = s.length() / 2;
        
        // 압축 단위 1 ~ n/2 반복문 
        for (int i = 1; i <= max_len; i++) {
            String tmp = ""; // 압축된 결과 String을 담아줄 변수
 
            int j = 0; // 어느 index부터 압축할 지 정하기 위한 변수
            while (true) {
                String split = s.substring(j); // 압축에 성공한 문자열을 제외
                
                // 만약 split의 길이가 압축 단위보다 작으면 split을 tmp 문자열에 담아주고
                // while문을 종료
                if (split.length() < i) {
                    tmp += split;
                    break;
                }
                
                split = split.substring(0, i); // 압축 단위만큼 잘라준다.
                j += i;
                int cnt = 1; // 자른 문자열이 몇 번 반복되는지 카운트한다.
                
                // 압축 기준이 되는 문자열이 앞에 위치하면
                // 카운트를 증가시켜준다.
                while (s.substring(j).indexOf(split) == 0) {
                    cnt++;
                    j += i;
 
                    if (j >= s.length())
                        break;
                }
 
                if (cnt == 1)
                    tmp += split;
                else
                    tmp += Integer.toString(cnt) + split;
 
                if (j >= s.length())
                    break;
            }
 
            if (tmp.length() < answer)
                answer = tmp.length();
        }
        return answer;
    }
 
}