prgms.60057 - 문자열 압축

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

        for (int unitSize = 1; unitSize <= s.length() / 2; unitSize++) {
            String convert = compress(s, unitSize);
            answer = Math.min(answer, convert.length());
        }

        return answer;
    }

    private String compress(String s, int i) {
        StringBuilder convert = new StringBuilder();
        String unit = s.substring(0, i);
        int count = 1;

        for (int j = i; j < s.length(); j += i) {
            if (j + i > s.length()) {
                convert.append(s.substring(j, s.length()));
                break;
            }
            String substring = s.substring(j, (j + i));
            if (unit.equals(substring)) {
                count++;
                continue;
            }
            if (count > 1) convert.append(Integer.toString(count));
            convert.append(unit);
            unit = substring;
            count = 1;
        }

        if (count > 1) convert.append(Integer.toString(count));
        convert.append(unit);

        return convert.toString();
    }
}

class Solution {
    public int solution(String s) {
        int answer = 0;

        for(int i=1; i<=(s.length()/2)+1; i++){
            int result = getSplitedLength(s, i, 1).length();
            answer = i==1 ? result : (answer>result?result:answer);
        }

        return answer;
    }

    public String getSplitedLength(String s, int n, int repeat){
        if(s.length() < n) return s;
        String result = "";
        String preString = s.substring(0, n);
        String postString = s.substring(n, s.length());

        // 불일치 -> 현재까지 [반복횟수 + 반복문자] 조합
        if(!postString.startsWith(preString)){
            if(repeat ==1) return result += preString + getSplitedLength(postString, n, 1);
            return result += Integer.toString(repeat) + preString + getSplitedLength(postString, n, 1);
        }

        return result += getSplitedLength(postString, n, repeat+1);
    }
}

다른 사람의 풀이2

비슷한 듯 하면서도 약간 다른 풀이이다. 상용로그로 자릿수를 구하는 아이디어는 정말… 수학에 능한 사람만이 떠올릴 수 있는 풀이인 것 같다. 나도 다음에 한 번 사용해 보아야겠다.

Tip

상용로그를 씌운 후, 1을 더하면 자릿수가 구해진다.

𝑵이 𝑛자리 수라면, 𝑵 = 10^(𝑛-1) × 𝛂 로 표현할 수 있다. (단, 0 ≤ 𝛂 < 1)

log𝑵 = log(10^(𝑛-1) × 𝛂) = 𝑛 - 1log10 + log𝛂 = (𝑛 - 1) + log𝛂

따라서 정수 부분은 (𝑛-1) 이다. 다시 말해, 자릿수는 정수부분보다 1만큼 크다.

class Solution {
    public int solution(String s) {
        int min = s.length();
        int len = s.length() / 2 + 1;
      
        for (int i = 1; i < len; i++) {
            String before = "";
            int sum = 0;
            int cnt = 1;
          
            for (int j = 0; j < s.length(); ) {
                int start = j;
                j = (j + i > s.length()) ? s.length() : j + i;
                String temp = s.substring(start, j);
              
                if (temp.equals(before)) {
                    cnt++;
                } else {
                    if (cnt != 1) {
                        sum += (int) Math.log10(cnt) + 1;
                    }
                    cnt = 1;
                    sum += before.length();
                    before = temp;
                }
            }
          
            sum += before.length();
            if (cnt != 1) {
                sum += (int) Math.log10(cnt) + 1;
            }
            min = (min > sum) ? sum : min;
        }

        return min;
    }
}