[프로그래머스/Level2] 문자열 압축 (Java)

문제

2020 KAKAO BLIND RECRUITMENT, https://programmers.co.kr/learn/courses/30/lessons/60057?language=java 

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

---

풀이

제한사항

문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘, 1개 단위로 잘라서 압축할 경우 반복되는 문자가 적을 경우 압축률이 낮음
ex) "aabbaccc" → "2a2ba3c" (문자가 반복되지 않아 한번만 나타난 경우 1은 생략)

문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는 방법
ex) 2개 단위로 잘라 압축 : "ababcdcdababcdcd" → "2ab2cd2ab2cd" 
8개 단위로 잘라 압축 : "ababcdcdababcdcd" → "2ababcdcd" (Good!)

2개 단위로 잘라 압축 : "abcabcdede" → "abcabc2de"
3개 단위로 잘라 압축 : "abcabcdede" → "2abcdede" (Good!)

압축을 위해 자르는 단위에 따라 압축률이 달라진다.
문자열마다 최상의 압축률을 가지는 단위가 다르다.

주어진 문자열 s를 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 구하라.

• s의 길이는 1 이상 1,000 이하
• s는 알파벳 소문자로만 구성

 

처리로직

• 반복되는 문자구간을 {반복횟수+문자} 형식으로 압축하는 과정
• 압축한 문자열이 가장 짧아지기 위해서는 해당 문자열 s에서 가장 긴 반복구간을 단위로 잡아야 한다.
• 1~s.length()/2 를 각 단위로 잡고 압축했을 때 결과 문자열 길이가 가장 짧은 단위를 찾는다.
  문제 목표가 문자열을 압축하는 것이기 때문에 s.length()/2 까지 단위만 유효하다. 예를 들어 문자 길이가 10인 "abcdeabced"와 같은 문자열이 있을 때 s.length()/2 값인 5 단위로 잘랐을 때가 최상의 압축률을 보이며(="2abcde"), s.length()/2 를 넘어가는 값으로 단위를 잡을 경우 길이 10의 문자열이 6 / 4로 잘리기 때문에 절대로 6크기 단위로 문자가 반복될 리 없다. (6단위로 반복되기 위해서는 최소 6*2=12크기의 문자열이 필요) 그렇기 때문에 s.length()/2 를 넘어가는 값을 단위로 잡는다는 건 압축을 하는데 무의미한 행동이다.
• substring(int start, int end) 메서드를 사용해 일정 단위로 문자열을 자른다. (*end 자리 값은 포함되지 않음)
• 자른 문자열들이 동일할 경우 하나로 압축 가능, 반복횟수를 증가한다.
• 다른 문자열이 나오는 순간, {반복횟수+문자}를 새로운 문자열에 추가

 

1개 단위로 압축 = "2a2ba3c" = 7

s.substring(0, 1)	s.substring(1, 2)	s.substring(2, 3)	s.substring(3, 4)	s.substring(4, 5)	s.substring(5, 6)	s.substring(6, 7)	s.substring(7, 8)
a	a	b	b	a	c	c	c

2개 단위로 압축 = "aabbaccc" = 8 (압축안됨)

s.substring(0, 2)	s.substring(2, 4)	s.substring(4, 6)	s.substring(6, 8)
aa	bb	ac	cc

 

코드

class Solution {
    public int solution(String s) {
        // 최단 문자열 길이
        int answer = Integer.MAX_VALUE;

        // 문자열 길이가 1인 경우 압축 불가
        if(s.length() == 1) return 1;

        // 0 ~ s.length()/2 단위로 차례로 압축
        for (int i = 1; i <= s.length() / 2; i++) {
            StringBuffer sb = new StringBuffer();   // 압축 결과 문자열
            String prevStr = "";                    // 비교용 이전 문자열
            int count = 1;                          // 연속 개수

            // 단위로 문자열 자르기
            for (int j = 0; j <= s.length() - i; j += i) {
                String curStr = s.substring(j, j + i);
                
                // 문자열 연속 여부 체크
                if (prevStr.equals(curStr)) {
                    count++;
                    continue;
                } else if (count > 1) {
                    sb.append(count + prevStr);     // 반복횟수+문자열 추가
                    count = 1;
                } else {
                    sb.append(prevStr);             // 문자열 추가
                }

                prevStr = curStr;                   // 비교 문자열 갱신
            }
            // 마지막 부분 추가
            sb.append(count > 1 ? count + prevStr : prevStr);

            // s의 길이가 압축 단위로 나누어 떨어지지 않을 경우, 남는 부분 추가
            if (s.length() % i != 0) {
                sb.append(s.substring(s.length() - s.length() % i, s.length()));
            }

            answer = Math.min(answer, sb.length());
            sb = new StringBuffer();
        }

        return answer;
    }
}

 

 

 

문자열 압축 과정을 살펴보기 위해 '일정한 단위로 잘린 문자열', '압축 결과 문자열'을 연산 도중에 출력해보았다.

public int solution(String s) {
    int answer = Integer.MAX_VALUE;

    if(s.length() == 1) return 1;

    for (int i = 1; i <= s.length() / 2; i++) {
        StringBuffer sb = new StringBuffer();
        String prevStr = "";
        int count = 1;

        
        for (int j = 0; j <= s.length() - i; j += i) {
            String curStr = s.substring(j, j + i);
            
            System.out.print(curStr + " / ");		// 단위 크기대로 잘린 부분문자열
            
            if (prevStr.equals(curStr)) {
                count++;
                continue;
            } else if (count > 1) {
                sb.append(count + prevStr);
                count = 1;
            } else {
                sb.append(prevStr);
            }

            prevStr = curStr;
        }
        
        sb.append(count > 1 ? count + prevStr : prevStr);

        if (s.length() % i != 0) {
            sb.append(s.substring(s.length() - s.length() % i, s.length()));
        }

        System.out.println("= " + sb.toString());	// 압축 결과 문자열
        
        answer = Math.min(answer, sb.length());
        sb = new StringBuffer();
    }

    return answer;
}

// 실행결과 ("aabbaccc")
a / a / b / b / a / c / c / c / = 2a2ba3c
aa / bb / ac / cc / = aabbaccc
aab / bac / = aabbaccc
aabb / accc / = aabbaccc
7