[Programmers] 2020카카오공채 문자열 압축

[Level 2]  문자열 압축

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

• 레벨 2 문제인데 문제를 제대로 이해하지 못해서 너무 오래 풀었다.. ㅠㅠ
• 압축할 문자열 s가 매개변수로 주어질 째, 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성하시오.
• 헷갈렸던 포인트는 문자열을 앞에서 부터 n개씩 잘라야한다는 부분이 n=2, aa/ab/aa/dd/ee/... 같이 연속해서 n개로 압축하는 것이 아니라 aa/abcabcd/rr/dd/... 처럼 첫 부분만 2개로 잘리면 뒷부분에서는 자유롭게 2개씩 묶어 압축하는 방식으로 이해했다. 노답스;; 

 

Solution

• 완전 탐색으로 1~s.length()/2 조각에 대해 전부 압축한 다음, 최소값을 return 하는 방식으로 풀이했다.
• s.length() % cut의 값인 exsit는 cut 보다 작은 조각 이므로 더이상 압축할 수 없어 마지막에 len 값으로 더해준다.

 

 

소스코드

import java.util.*;
class Solution {
  public static int solution(String s) {
        int answer = s.length();
        int cut = 0;
        while (cut++ < s.length() / 2) {
            int count = 1;
            String prev = s.substring(0, cut);
            String cur = null;
            int len = 0;
            String exist = s.substring(s.length() - s.length() % cut);
            for (int i = cut; i <= s.length() - (exist.length() + cut); i += cut) {
                cur = s.substring(i, i + cut);
                if (prev.equals(cur)) {
                    count++;
                } else {
                    if (count > 1) {
                        len += prev.length() + Integer.toString(count).length();
                    } else {
                        len += prev.length();
                    }
                    count = 1;
                    prev = cur;
                }
            }
            if(count > 1) len += prev.length() + Integer.toString(count).length();
            else len += prev.length();
            answer = Math.min(answer, len + exist.length());
        }
        return answer;
    }
}