[알고리즘] 2020 KAKAO BLIND RECRUITMENT 문자열 압축 🪨

문제 및 풀이 설명

알파벳으로 이루어진 문자열이 존재한다. 예를 들어 "aabbaccc" 이런 문자열이 존재한다면 먼저 문자열을 1개 단위로 쪼개서 각각의 다음 문자열들과 비교를 한다. 해당 문자가 다음 문자와 같을 경우 cnt라는 변수의 값을 1 증가시켜서 같은 문자의 맨 앞에 몇 개의 같은 수가 있는지 적는다. 연속되는 문자열이 존재하지 않을 시에는 cnt 값을 증가시키지 않고 해당 문자열을 그대로 적은 다음 다른 문자열로 넘어간다. "2a2ba3c" 이렇게 변하게 될 것이다.
또 다른 예시를 들면, "ababcdcdababcdcd" 의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd" 로 표현할 수 있다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd" 로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법이 된다.
맨 처음 문제에 접근했을때는, 문자열의 개념을 적용시킬 생각을 하지 못하고 그저 배열로만 접근을 하려고 했었다. 현재 연산되고 있는 문자열을 임시로 가지고 있는 배열과, 오른쪽으로 이동하며 계속해서 비교 대상이 되어줄 배열.. 이런 식으로 접근을 하려하니 배열이 늘어날수록 반복문도 늘어나고 정말 비효율적이고 복잡한 코드가 되어갔다. 결국 적용시켜야 하는 개념이 subString으로 두 개의 문자열을 비교하는 방식이였다.

적용 시킨 개념

subString
equals

Code

public static String solution(String s) {
    String answer = "";
    int j = 0;
    for (int i = 1; i <= s.length() / 2; i++) {
        String result = "";
        String left = s.substring(0, i);
        int cnt = 1;
        for (j = i; j <= s.length(); j += i) {
            String right = "";
            if ((j + i) >= s.length()) {
                right = s.substring(j);
            } else {
                right = s.substring(j, j + i);
            }
            if (left.equals(right)) {
                cnt++;
            } else {
                if (cnt > 1) {
                    result += cnt;
                }
                result += left;
                left = right;
                cnt = 1;
            }
        }
        result += left;
        answer += result + " ";
    }
    return answer;
}

1️⃣ 왼쪽에서 비교되는 문자열은 총 문자열 길이의 절반 길이 까지만을 캐싱

첫 번째 for문에서는 왼쪽에서 비교 될 문자열을 캐싱하고 있는다. result를 빈 문자열로 초기화 시켜주는 이유는 안쪽에서 모든 연산이 완료되고 나면 result는 해당되는 길이만큼의 문자열을 잘라서 비교 한 결과를 가지고 있게 되고, 이 결과에 대한 문자열의 길이를 다시 초기화 해 줘야 다음 비교 할 문자열을 가질 수 있기 때문이다. 문제에서는 각각의 길이만큼 잘라서 비교를 한 뒤 결과적으로 총 길이가 가장 짧은 문자열의 길이를 return 하라고 하였기 때문이다. 또한 이 문제에서는 subString의 개념에 대해 잘 이해가 되어야 할 것 같다. 인자 두 개를 받을 때, 첫 번째 인자는 자르고 싶은 시작점을 의미하고 두 번째 인자는 자르고싶은 문자 바로 다음 번째 문자를 의미한다.

2️⃣ 안쪽의 for문에서는 왼쪽, 오른쪽 문자열을 캐싱

중첩되는 for문에서는 바로 상위 for문에서 가지고 있는 문자열과 계속 반복해서 비교를 시도한다. 왼쪽의 값(left)은 안쪽에서 문자열 길이가 끝나고 상위 for문이 다시 길이를 늘린 문자열로 비교를 시도할 때 초기화 되고, 비교를 할 때 값이 같다면 cnt 값을 1씩 증가시키고 i 즉, 비교해야하는 문자열의 길이 i 만큼 j를 증가시켜 준 후 그 다음 비교 대상인 right로 넘어가게 된다. j + i가 총 문자열의 길이를 넘게되는 시점은 왼쪽에서 캐싱하고 있는 부분이 오른쪽에 있는 값이랑 길이가 맞지 않을 때 발생한다. 예를 들어, "aabbaccc" 문자열에서 처음에 "abc"와 "bac"를 비교했을 때 값이 같지 않아 left 값이 "bac"로 초기화 되었을거고, 이 시점에서 남은 right 값은 cc 이 문자열이 될 것이다. 또한 j는 6의 값을 가지고 있고 이때 i만큼의 값인 3을 더하게 되면 총 문자열의 길이인 8을 넘게된다. 따라서 이때는 cc라는 문자열이 남아있는 상태에서 for문은 총 문자열의 길이를 초과하였으므로 연산을 수행하지 않게 된다. 이 허점을 막기 위해서 안쪽 for문이 끝나는 시점에 result += left 라는 연산을 추가 해 주어 마지막에 남은 문자열 까지 result에 담아서 캐싱을 할 수 있게 되었다.

3️⃣ 비교하는 문자열이 같을 경우와 다를 경우

반복문 안에서 left와 right가 동일할 경우와 다를 경우가 존재한다. 먼저 비교하는 값이 같다면 left 값은 그대로 유지한 채 cnt 값을 증가시키고, 다시 right 값만 인덱스를 i만큼 증가시킨 다음 비교를 진행한다. 비교하는 문자열이 다를 경우에는 지금까지 가지고있던 cnt값을 result에 먼저 누적시켜주고, 그 다음 left 즉, 기준이 되는 문자열을 cnt값이 저장된 result에 붙여줌으로 기준이 되는 문자열(left)이 몇 번 반복이 되었는지 result에 저장 해 준다. 이러한 과정을 반복하면 result에는 문자열의 총 길이의 절반만큼 계속해서 반복이 된 여러가지 경우의 결과 문자열들을 얻을 수 있고 이를 이용하여 result에 누적된 모든 결과들의 각각의 길이를 계산 한 후 원하는 가장 압축이 많이 된 문자열의 길이를 return 받을 수 있다.