[프로그래머스] 60057. 문자열 압축

문제 링크

[프로그래머스] 60057. 문자열 압축

풀이 과정

자를 문자열 개수 단위를 delta 로 두고, 1을 시작으로 기준 개수를 하나씩 올립니다. 예를 들어 delta 가 각각 1일 경우와 2일 경우, 아래 그림과 같이 문자열이 잘라지게 됩니다.

delta = 1

delta = 2

이후에는 현재까지 압축이 완료된 문자열을 의미하는 sb 에 잘린 문자열에 압축을 적용합니다.

• sb 문자열이 아직 비어있다면, 문제에서 반복되지 않아 한 번 나타난 경우는 1을 생략하므로, 잘린 문자열을 그냥 붙입니다.
• sb 문자열이 잘린 문자열 무언가로 구성되어 있다면, 가장 최근에 붙인 문자열을 잘린 문자열과 비교합니다. 이 때, 둘이 같다면 압축을 진행해 개수를 증가시킵니다.

int countIndexEnd = sb.length() - delta - 1;

if (Character.isDigit(sb.charAt(countIndexEnd))) {
	...
}

가장 최근에 압축이 끝난 문자열은 sb 마지막에 붙어져 있습니다. 해당 문자열 앞에는 숫자가 있을 수도, 없을 수도 있습니다. 숫자가 있는 경우는 압축된 문자열이 2개 이상 있음을 의미하며, 숫자가 없는 경우는 잘린 문자열이 이전과 동일하지 않아 반복이 일어나지 않았음을 의미합니다. 따라서 먼저 이 앞에 숫자가 있는 지 없는 지를 판단해 봐야 했습니다.

숫자인 경우는 해당 숫자를 1 만큼 증가 시켜줘야 하고, 숫자가 아닌 경우 앞에 2를 새롭게 붙여주는 작업을 진행해야 합니다. 또한 앞에 숫자가 두 자리 이상인 경우도 생각해주어야 합니다. 예를 들어, sb가 ...10ab , 현재 잘린 문자열이 ab 라면, 압축은 ...11ab 로 진행되어야 할 것입니다.

int countIndexStart = countIndexEnd - 1;

while (countIndexStart >= 0 && Character.isDigit(sb.charAt(countIndexStart)))
    countIndexStart--;
countIndexStart++;

int count = Integer.parseInt(sb.substring(countIndexStart, countIndexEnd + 1));

sb.replace(countIndexStart, countIndexEnd + 1, Integer.toString(count + 1));

따라서 countIndexStart 인덱스를 두어 숫자가 시작하는 인덱스를 찾고 countIndexStart 부터 countIndexEnd 까지의 문자열을 파싱해 정수값 개수를 구한 뒤 1을 더해 해당 범위를 통째로 replace 해줬습니다.

코드

Java

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

        for (int delta = 1; delta < s.length(); delta++) {
            StringBuffer sb = new StringBuffer();

            int start = 0, end = 0 + delta;

            while (start != end && end <= s.length()) {
                String splited = s.substring(start, end);

                if (sb.length() == 0) {
                    sb.append(splited);
                } else {
                    String prev = sb.substring(sb.length() - delta, sb.length());

                    if (prev.length() != 0 && prev.equals(splited)) {
                        int countIndexEnd = sb.length() - delta - 1;

                        if (countIndexEnd >= 0) {
                            if (Character.isDigit(sb.charAt(countIndexEnd))) {
                                int countIndexStart = countIndexEnd - 1;

                                while (countIndexStart >= 0 && Character.isDigit(sb.charAt(countIndexStart)))
                                    countIndexStart--;
                                countIndexStart++;

                                int count = Integer.parseInt(sb.substring(countIndexStart, countIndexEnd + 1));

                                sb.replace(countIndexStart, countIndexEnd + 1, Integer.toString(count + 1));
                            } else {
                                sb.insert(countIndexEnd + 1, "2");
                            }
                        } else {
                            sb.insert(0, "2");
                        }
                    } else {
                        sb.append(splited);
                    }
                }

                start = end;
                end = ((start + delta) > s.length()) ? s.length() : start + delta;
            }

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

        return answer;
    }

    public static void main(String[] args) {
        solution("aabbaccc");
//        solution("ababcdcdababcdcd");
//        solution("abcabcdede");
//        solution("abcabcabcabcdededededede");
//        solution("xababcdcdababcdcd");
//        solution("xxxxxxxxxxyyy");
    }
}

Javascript

function ReplaceAt(input, replace, start, end) {
    let tmp = [];
    for (let idx = 0; idx < replace.length; idx++) tmp.push(replace[idx]);

    let arr1 = input.slice(0, start);
    let arr2 = input.slice(end + 1);

    input.splice(start, end - start + 1);

    return arr1.concat(tmp, arr2);
}

function solution(s) {
    let answer = s.length;

    for (let delta = 1; delta < s.length; delta++) {
        let sb = [];

        let start = 0,
            end = 0 + delta;

        while (start != end && end <= s.length) {
            let splited = s.substring(start, end);

            if (sb.length == 0) {
                for (let idx = 0; idx < splited.length; idx++) {
                    sb.push(splited[idx]);
                }
            } else {
                let prev = sb.slice(sb.length - delta, sb.length).join("");

                if (prev.length != 0 && prev === splited) {
                    let countIndexEnd = sb.length - delta - 1;

                    if (countIndexEnd >= 0) {
                        if (!isNaN(sb[countIndexEnd])) {
                            let countIndexStart = countIndexEnd - 1;

                            while (countIndexStart >= 0 && !isNaN(sb[countIndexStart]))
                                countIndexStart--;
                            countIndexStart++;

                            let count = parseInt(sb.slice(countIndexStart, countIndexEnd + 1).join(""));
                            sb = ReplaceAt(sb, count + 1 + "", countIndexStart, countIndexEnd);
                        } else {
                            sb.splice(countIndexEnd + 1, 0, "2");
                        }
                    } else {
                        sb.splice(0, 0, "2");
                    }
                } else {
                    for (let idx = 0; idx < splited.length; idx++) {
                        sb.push(splited[idx]);
                    }
                }
            }

            start = end;
            end = start + delta > s.length ? s.length : start + delta;
        }

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

    return answer;
}

solution("aabbaccc");
// solution("ababcdcdababcdcd");
// solution("abcabcdede");
// solution("abcabcabcabcdededededede");
// solution("xababcdcdababcdcd");
// solution("xxxxxxxxxxyyy");