[프로그래머스/자바] 문자열 압축 풀이 - 2020 KAKAO BLIND RECRUITMENT

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

프로그래머스

 

2020 KAKAO BLIND RECRUITMENT Level 2 문제다.

 

 

 

압축한 문자열 중 가장 짧은 길이를 찾기 위해 

1부터 직접 압축하여 문자열을 생성하고 길이를 비교한다.

문자열 길이의 반 이상 단위로 압축할 수는 없으므로

1부터 문자열 길이의 반까지만 압축한다.

 

압축할 단위의 길이 i만큼 문자열을 자르고(delim), 그 뒤의 문자열이 자른 문자열로 시작하는지 확인한다.

자른 문자열로 시작한다면 cnt를 증가시켜 얼마나 반복되는지를 구한다.

자른 문자열로 시작하지 않는다면 delim을 그 다음 i만큼의 문자열로 변경한다.

다시 새로운 delim으로 시작하는지를 반복하며 문자열 끝까지 확인한다.

 

그리고 압축하여 만든 문자열의 길이와 ans(초기값은 문자열 s의 길이)를 비교하여

더 작은 값을 ans에 저장한다.

 

 

class Solution {
    public int solution(String s) {
        int len = s.length();
        int ans = s.length();

        // 1부터 문자열의 길이의 반까지의 단위로 잘라 압축
        for(int i=1;i<=s.length() / 2;i++) {
            StringBuilder sb = new StringBuilder();
            String delim = s.substring(0, i);

            int cnt = 1; // 문자 출현 횟수
            int start = i; // substring 시작 인덱스
            while(start < len) {
                if(s.substring(start, len).startsWith(delim)) {
                    cnt++;
                }
                else { 
                    if(cnt == 1) sb.append(delim);
                    else sb.append(cnt).append(delim);
                    cnt = 1;
                    delim = start + i < len ? s.substring(start, start + i) : s.substring(start, len);
                }
                start += i;
            }
            if(cnt == 1) sb.append(delim);
            else sb.append(cnt).append(delim);
            ans = Math.min(ans, sb.toString().length());
        }
        return ans;
    }
}