[60057] 문자열 압축

✔ 문자열 압축

[프로그래머스 60057]

문제 분석하기

문자열을 자를 수 있는 단위는 1개부터 문자열의 길이 / 2까지이므로 이에 대해 압축했을 때 가장 짧은 것의 길이를 찾도록 함

손으로 풀어보기

1. 문자열을 자를 수 있는 단위를 1개부터 문자열의 길이 / 2까지 하여 압축
   
   • 문자열을 단위로 잘라가며 앞의 문자와 동일할 경우 반복 횟수 증가
   • 문자열을 단위로 잘라가며 앞의 문자와 동일하지 않으며 반복 횟수가 1보다 크다면 반복 횟수와 문자열을 저장
   • 문자열을 단위로 잘라가며 앞의 문자와 동일하지 않으며 반복 횟수가 1이라면 문자열을 저장
   • 단위로 나누어 떨어지지 않는 부분은 그대로 문자열에 저장
   • 이후 저장한 압축한 문자열의 길이를 비교하여 가장 최소 값으로 계속해서 갱신
2. 가장 짧은 것의 길이를 반환

슈도코드 작성하기

s(압축할 문자열)
answer(1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이) = s의 길이로 초기화
for(i -> 1부터 s/2의 길이까지) {
    sb(압축 결과 문자열)
    prev(이전 문자열) = s를 0부터 i까지 자른 문자열로 초기화
    now(현재 문자열)
    count(반복 횟수) = 1로 초기화
    for(j -> i부터 s의 길이까지, j는 i 단위씩 증가) {
        if(j + i가 s의 길이보다 크거나 같다면)
            now = s를 j부터 s의 길이까지 자른 문자열
        else 
            now = s를 j부터 j + i까지 자른 문자열
        if(prev와 now가 같다면)
            count 증가
        else if(count가 1이라면) {
            sb에 prev 추가
            prev를 now로 갱신
        }
        else {
            sb에 count와 prev 추가
            prev를 now로 갱신
            count를 1로 초기화
        }
    }
    if(i와 prev의 길이가 다르다면)
        남는 문자열이므로 sb에 나머지인 prev 저장
    answer을 Math.min(answer, sb의 길이)로 갱신
}
answer 반환

코드 구현하기

/**
 * 60057) 문자열_압축
 */
public class L054_60057 {
    // s(압축할 문자열)
    public int solution(String s) {
        // answer(1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이)
        int answer = s.length();
        for (int i = 1; i <= s.length() / 2; i++) {
            // sb(압축 결과 문자열)
            StringBuilder sb = new StringBuilder();
            // prev(이전 문자열)
            String prev = s.substring(0, i);
            // now(현재 문자열)
            String now = "";
            // count(반복 횟수)
            int count = 1;
            for (int j = i; j <= s.length(); j += i) {
                // j + i가 s의 길이보다 크거나 같다면
                if (j + i >= s.length())
                    // s를 j부터 s의 길이까지 자른 문자열
                    now = s.substring(j, s.length());
                // j + i가 s의 길이보다 작다면
                else
                    // s를 j부터 j + i까지 자른 문자열
                    now = s.substring(j, j + i);
                // prev와 now가 같다면
                if (prev.equals(now))
                    // count 증가
                    count++;
                // count가 1이라면
                else if (count == 1) {
                    // sb에 prev 추가
                    sb.append(prev);
                    // prev를 now로 갱신
                    prev = now;
                }
                // count가 1보다 크다면
                else {
                    // sb에 count와 prev 추가
                    sb.append(count).append(prev);
                    // prev를 now로 갱신
                    prev = now;
                    // count를 1로 초기화
                    count = 1;
                }
            }
            // i와 prev의 길이가 다르다면
            if (i != prev.length())
                // 남는 문자열이므로 sb에 나머지인 prev 저장
                sb.append(prev);
            // answer을 Math.min(answer, sb의 길이)로 갱신
            answer = Math.min(answer, sb.length());
        }
        // answer 반환
        return answer;
    }

    // 테스트 케이스
    public static void main(String[] args) {
        L054_60057 solution = new L054_60057();

        String s = "aabbaccc";

        int result = solution.solution(s);

        System.out.println(result);
    }
}