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

🔗 문제 링크

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

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

 

📝 풀이 과정

길이 순으로 실제 압축을 구현해 가장 작은 길이를 반환하는 문제이다. 길이는 1부터 문자열 길이의 절반까지 가능한데, 어차피 문자열의 길이의 절반 이상으로 압축을 시도해도 같은 문자열을 반복할 수 없기 때문이다.

 

이후, 반복문을 돌며 앞의 문자열과 같은 문자열이라면 cnt를 증가시켜주고 아니라면 반복문을 탈출해 실제 문자열이 아닌 길이만 알면 되기때문에 문자열 자체가 아닌 길이를 더해준다. 만약 cnt의 크기가 1이 아니라면 길이에 숫자에 Math.log10() + 1을 한만큼 더해주었다.

 

💡 Math.log10(int n)은 $\log n$을 한 결과가 double값으로 나오게 되는데 이를 int에 대입하면서 자동으로 소수점 아래값이 버려지게 된다.

ex) Math.log10(7) = 0.xxxx = 0

 

만약 잘라주는 길이가 문자열의 약수가 아니라면 남는 문자열이 나오게 되고, 남는만큼 길이에 추가로 더해주면 된다. 계산한 길이가 기존 길이보다 짧다면 갱신해주고 최종적으로 가장 짧았던 길이를 반환해주면 된다.

 

 

 

💻 코드

class Solution {
    public int solution(String str) {
        int min = str.length();

        for (int s = 1; s <= str.length() / 2; s++) {
            String prev;
            int idx = 0, cnt = 0, len = 0;

            for (; idx + s <= str.length(); cnt = 0) {
                prev = str.substring(idx, idx + s);
                while (idx + s <= str.length() && prev.equals(str.substring(idx, idx + s))) {
                    cnt++;
                    idx += s;
                }
                len += s + (cnt == 1 ? 0 : Math.log10(cnt) + 1);
            }
            min = Math.min(len + str.length() % s, min);
        }
        return min;
    }
}