[프로그래머스] 문자열 압축 - JAVA

프로그래머스 문자열 압축 - JAVA

---

문제 설명이 너무 길어 생략

[문제 보기] : https://programmers.co.kr/learn/courses/30/lessons/60057

문제 풀이

문자열의 길이를 n이라고 할 때 문자열을 1부터 n/2까지 쪼개며 압축시킨 경우를 전부 확인해봐야하는 완전탐색 유형의 문제이다.
단위별로 총 압축했을 때의 문자열 길이에 압축이 1이상 가능한 경우 압축했을때의 문자열 길이를 더하는 방식으로 단위별 길이를 구할 수 있다. 문자열 s를 순회하며 단위별로 짤라 비교하며 압축 여부를 찾아 길이를 구하는 방식이다.

저처럼 반복횟수가 1인 경우 자르는 길이만큼 더하고, 그 이상인 경우 자르는 길이와 반복 횟수(10이상인경우 2칸 차지하므로 생각해서 더해야 한다)의 길이를 더하는 방식이 있고, 문자열을 더하는 방식으로 푸는 방법도 있다.

소스 코드

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

        for (int i = 1; i <= s.length() / 2; i++) {
            int len = 0, j = 0;

            while (j <= s.length() - i) {
                String unit = s.substring(j, j + i);

                int cnt = 0;
                for ( ; j <= s.length() - i; j += i) {
                    if (unit.equals(s.substring(j, j + i))) {
                        cnt++;
                    } else {
                        break;
                    }
                }

                if (cnt == 1) {
                    len += i;
                }
                else {
                    len += (String.valueOf(cnt).length() + i);
                }
            }

            len += s.length() - j;
            answer = Math.min(answer, len);
        }

        return answer;
    }
}