29 July 2020 / ALGORITHM

프로그래머스 - 문자열 압축 [2020 KAKAO BLIND RECRUITMENT]

카카오 블라인드 2020 문자열 압축 문제를 설명과 함께 풀이 합니다.

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

문제바로가기

문제유형

Brute-Force

문제 설명

주어진 문자열을 압축하는 문제

aabbaccc => 2a2ba3c 각 중복되는 문자열앞에 중복개수를 붙여준다.
단 1개짜리 문자열은 개수를 붙이지 않는다.
ababcdcdababcdcd => 경우 2ab2cd2ab2cd 보다 2ababcdcd 가 문자열 길이가 더 짧다.

결론 적으로는 각각의 케이스를 다 조사해서 제일 작은 문자열 길이를 리턴해야한다.

풀이법

처음에는 for문 하나에서 앞자리 문자와 다음 문자열을 비교 하면서 처리하려고 하였다.
aabbaccc케이스는 문자 1개씩만 비교하니 통과하는 로직이지만 ababcdcd == ababcdcd 비교 로직이 들어가야 되기 때문에 for문 하나로는 안된다. 결국 전체 케이스를 다 확인 해야한다.

aabbaccc를 압축 하는 예

aabbaccc

a-a a-b b-b b-a a-c c-c c-c <= 한칸씩 옮겨가며 조합을 본다.

aa-bb bb-ac ac-cc <= 두개씩 잘라서 조합을 본다.

aab-bac bac-cc <= 3개씩 잘라서 조합을 본다.

aabb-accc 4개씩 잘라서 조합을 본다.

총문자 열이 8개 이므로 1/2인 4개 즉 1~4개 까지 잘라서 비교해보는 로직을 구성하는 방법으로 해결한다.

소스코드

public class Lessons60057 {
    public static int solution(String s) {
        int result = s.length();

        for (int i = 1; i <= s.length() / 2; i++) {
            StringBuilder zipStr = new StringBuilder();
            String str = "", prevStr = "";
            int strCount = 1;

            for (int j = 0; j < s.length(); j += i) {
                str = s.substring(j, Math.min(j + i, s.length()));

                if (prevStr.equals(str)) {
                    strCount++;
                    continue;
                }

                zipStr.append(strCount > 1 ? strCount + prevStr : prevStr);
                prevStr = str;
                strCount = 1;
            }

            zipStr.append(strCount > 1 ? strCount + str : str);
            result = Math.min(result, zipStr.length());
        }

        return result;
    }
}