2020 카카오 신입 공채 : 문자열 압축

문자열 압축

프로그래머스 문자열 압축

해설

aabbaccc -> 2a2ba3c
s 의 길이는 1 <= s <= 1000
s 는 알파벳 소문자로만 이루어져 있음
문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return

min (1개단위로 잘랐을 때의 결과 vs 2개 ..)
min (2개단위로 잘랐을 때의 결과 vs 3개 ..)
...

압축 최대 효율은 -> 2 * 반복되는 문자열

압축 최대 효율은 2번 압축 되는 경우 가장 짧은 문자열로 압축이 된다.

1개 단위로 반복되는 문자를 압축하는 경우

* 예시 입력 1
* KKHSSSSSSSE
*
* 예시 출력 1
* K2HS7E

// i 번째랑 i + 1 번째의 문자를 비교한다.
public String solution2(String s){
    String answer="";
    s=s+" ";
    int cnt=1;
    for(int i=0; i<s.length()-1; i++){
        if(s.charAt(i)==s.charAt(i+1)) cnt++;
        else{
            answer+=s.charAt(i);
            if(cnt>1) answer+=String.valueOf(cnt);
            cnt=1;
        }
    }
    return answer;
}

구현

1개 단위로 반복되는 문자를 압축하는 경우의 로직을 가지고, 이중 반복문을 생각하여 구현하면 된다.

public class Solution {

    static int answer;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println(solution(sc.nextLine()));
    }

    public static int solution(String alphabet) {
        // 구하고자하는 답을 원본 문자열의 길이로 초기화
        answer = alphabet.length();

        // 1 ~ alphabet.length/2 만큼의 단위로 문자열 자르기
        for (int i = 1; i <= alphabet.length() / 2; i++) {
            int count = 1;

            // i 개 단위로 자른 문자열
            String current = alphabet.substring(0, i);
            StringBuilder stringBuilder = new StringBuilder();

            // i 개 단위로 잘린 현재 문자열(current) 와 비교하기 위한 next 문자열 구하는 반복문
            for (int k = i; k < alphabet.length(); k = k + i) {
                int nextLastIndex = Math.min(k + i, alphabet.length());
                String next = alphabet.substring(k, nextLastIndex);

                if (current.equals(next)) {
                    count++;
                } else {
                    appendToStringBuilder(stringBuilder, count, current);
                    count = 1;
                    current = next;
                }
            }

            // Ex. alphabet 길이가 16이고 3개 단위로 자른다고 했을때, 내부 반복문의 k 값은 15 까지만 가능함.
            // 따라서 내부 반복문 끝나면 한 번더 남은 문자열을 붙여줘야 함
            appendToStringBuilder(stringBuilder, count, current);

            answer = Math.min(answer, stringBuilder.length());
        }

        return answer;
    }

    static void appendToStringBuilder(StringBuilder stringBuilder, int count, String str) {
        if(count > 1) {
            stringBuilder.append(count);
        }
        stringBuilder.append(str);
    }
}