[2020 KAKAO BLIND RECRUITMENT] 문자열 압축

[2020 KAKAO BLIND RECRUITMENT] 문자열 압축

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

 

 

 문자열을 압축하여 길이를 출력하는 문제이다. 눈으로 보기에는 간단해 보였지만 문자열 조작에 익숙하지 않아 생각보다 난잡한 코드가 되었다. 최대한 혼자 힘으로 풀기 위해 노력했다. 제출까지 완료하였지만 코드가 난잡하고 읽기도 힘든 부분이 많다. 문자열을 생성하고 더하는 부분에서 Stirng 클래스를 사용하여 문자열을 조합했기 때문에 메모리 사용이 많다. 

 

public class StringCompression {

    static int solution(String s) {
        int answer = 0;

        int minLength = Integer.MAX_VALUE;

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

        for (int i = 1; i <= s.length() / 2; i++) { // 반절까지 비교가 가능하기 때문에 0 ~ 길이의 반까지 반복
            String prev = s.substring(0, i);
            int count = 1;
            String tempString = "";
            for (int j = i; j <= s.length() - i; j += i) {
                String current = s.substring(j, j + i);
                if (prev.equals(current)) {
                    ++count;
                } else if (count != 1) {
                    tempString = tempString + count + prev;
                    count = 1;
                } else {
                    tempString = tempString + prev;
                }
                prev = current;
            }

            prev = s.substring(s.length() - i - (s.length() % i));
            if (count != 1) {
                tempString = tempString + count + prev;
            } else if (count == 1)
                tempString = tempString + prev;
            if (minLength > tempString.length()) minLength = tempString.length();
        }

        answer = minLength;

        return answer;
    }

    public static void main(String[] args) {
        String[] inputs = {
                "aabbaccc",
                "ababcdcdababcdcd",
                "abcabcdede",
                "abcabcabcabcdededededede",
                "xababcdcdababcdcd",
                "xxxxxxxxxxyyy",
                "a"
        };

        for (String s : inputs) {
            System.out.println(solution(s));
        }
    }
}

 

 이중 루프로 처리하였기 때문에 시간 복잡도는 O(n²)으로 예상된다. 첫 번째 루프는 비교할 문자열의 길이를 1부터 도는 루프이고, 두번째 루프는 문자열을 비교할 길이 만큼 잘라서 비교하기 위한 루프이다.

 

 비교적 단순한 코드 이지만 문제를 해결하는데 에만 집중한 탓에 입력된 문자열 s가 1일 때와 비교할 문자열이 마지막을 의미할 때 의도적으로 if를 넣어 회피하는 부분이 맘에 들지 않는다. 

 

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

 

prev = s.substring(s.length() - i - (s.length() % i));
if (count != 1) {
    tempString = tempString + count + prev;
} else if (count == 1) 
    tempString = tempString + prev;
if (minLength > tempString.length()) minLength = tempString.length();

 

---

 방학 중 교수님이 진행하시는 특강을 기반으로 다시 한 번 문제를 이해하고 코드를 수정하였다. 총 3단계에 걸쳐 코드를 보완하고, 최종적으로 문제에서의 요구사항에 맞추어 solution을 해결하였다. 우선 문자열의 길이가 1이라고 가정하고 간단한 압축 관련 문제라고 생각하고 풀이하였다. 코딩 테스트에 쉬운 문자열 문제로 종종 나올 수 있는 문제라고 한다.

 

public class StringCompression_1 {

    static int compress(String s) {
        StringBuilder stringBuilder = new StringBuilder();
        char prev = s.charAt(0);
        int count = 1;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == prev) ++count;
            else {
                if (count > 1) stringBuilder.append(count);
                stringBuilder.append(prev);
                prev = s.charAt(i);
                count = 1;
            }
        }

        if (count > 1) stringBuilder.append(count);
        stringBuilder.append(prev);

        System.out.print("압축된 문자열 : " + stringBuilder.toString() + " 길이 : ");

        return stringBuilder.length();
    }

    public static void main(String[] args) {
        String[] inputs = {
                "aabbaccc",
                "ababcdcdababcdcd",
                "abcabcdede",
                "abcabcabcabcdededededede",
                "xababcdcdababcdcd",
                "xxxxxxxxxxyyy",
                "a"
        };

        for (String s : inputs) {
            System.out.println(compress(s));
        }
    }
}

 

압축된 문자열 : 2a2ba3c 길이 : 7
압축된 문자열 : ababcdcdababcdcd 길이 : 16
압축된 문자열 : abcabcdede 길이 : 10
압축된 문자열 : abcabcabcabcdededededede 길이 : 24
압축된 문자열 : xababcdcdababcdcd 길이 : 17
압축된 문자열 : 10x3y 길이 : 5
압축된 문자열 : a 길이 : 1

 

 StringBuilder를 사용했기 때문에 문자열 추가 과정에서 상당 부분 메모리 사용을 줄였다. 한 개의 문자열만 비교하기 때문에 charAt을 사용하여 해당 index의 char만 비교하면 된다. char는 기본 자료형 이기 때문에 간단하게 == 연산자로 두 문자를 비교할 수 있었다. 

 

 이제는 문자열을 n의 길이로 잘라서 비교하는 compress 메소드로 변경해보자.

 

public class StringCompression_2 {

    static int compress(String s, int n) {
        StringBuilder stringBuilder = new StringBuilder();
        String prev = s.substring(0, n);
        int count = 1;

        for (int i = n; i <= s.length() - n; i += n) {
            String tempString = s.substring(i, i + n);
            if (tempString.equals(prev)) ++count;
            else {
                if (count > 1) stringBuilder.append(count);
                stringBuilder.append(prev);
                prev = tempString;
                count = 1;
            }
        }

        if (count > 1) stringBuilder.append(count);
        stringBuilder.append(prev);
        int tail = s.length() % n;
        if (tail > 0) stringBuilder.append(s.substring(s.length() - tail));

        System.out.print("압축된 문자열 : " + stringBuilder.toString() + " 길이 : ");

        return stringBuilder.length();
    }

    public static void main(String[] args) {
        String s = "abcabcdede";

        for (int i = 1; i < s.length(); i++) {
            System.out.println(compress(s, i));
        }
    }
}

 

압축된 문자열 : abcabcdede 길이 : 10
압축된 문자열 : abcabc2de 길이 : 9
압축된 문자열 : 2abcdede 길이 : 8
압축된 문자열 : abcabcdede 길이 : 10
압축된 문자열 : abcabcdede 길이 : 10
압축된 문자열 : abcabcdede 길이 : 10
압축된 문자열 : abcabcdede 길이 : 10
압축된 문자열 : abcabcdede 길이 : 10
압축된 문자열 : abcabcdede 길이 : 10

 

 문자열 패턴의 크기 만큼 루프를 돌며 비교한다. 추가된 부분은 압축할 문자열의 길이의 나머지가 생기는 경우, 추가적으로 꼬리부분은 따로 붙여줘야 한다. 

 

 마지막으로 문제에서는 문자열 출력은 없고 단순히 길이만 출력하기 때문에 StringBuilder를 사용하지 않아도 된다.

 

public class StringCompression_3 {

    static int compress(String s, int n) {
        int result = 0;
        String prev = s.substring(0, n);
        int count = 1;

        for (int i = n; i <= s.length() - n; i += n) {
            String tempString = s.substring(i, i + n);
            if (tempString.equals(prev)) ++count;
            else {
                if (count > 1) result += String.valueOf(count).length();
                result += n;
                prev = tempString;
                count = 1;
            }
        }

        if (count > 1) result += String.valueOf(count).length();
        result += n;
        result += s.length() % n;

        System.out.print("길이 : ");

        return result;
    }

    public static void main(String[] args) {
        String s = "abcabcdede";

        for (int i = 1; i < s.length(); i++) {
            System.out.println(compress(s, i));
        }
    }
}

 

 길이 : 10
 길이 : 9
 길이 : 8
 길이 : 10
 길이 : 10
 길이 : 10
 길이 : 10
 길이 : 10
 길이 : 10

 

 문자열의 길이만 가지고 연산을 진행하였다. 앞선 방법과는 다르게 메모리 사용도 적고, 간단한 연산만으로 해결할 수 있었다. 

 

 이제 앞선 3단계를 합쳐 최종적인 solution 해결을 위한 코드이다.

 

public class StringCompression_solution {

    static int compress(String s, int n) {
        int result = 0;
        String prev = s.substring(0, n);
        int count = 1;

        for (int i = n; i <= s.length() - n; i += n) {
            String tempString = s.substring(i, i + n);
            if (tempString.equals(prev)) ++count;
            else {
                if (count > 1) result += String.valueOf(count).length();
                result += n;
                prev = tempString;
                count = 1;
            }
        }

        if (count > 1) result += String.valueOf(count).length();
        result += n;
        result += s.length() % n;

        return result;
    }

    static int solution(String s) {
        int min = Integer.MAX_VALUE;
        for (int i = 1; i <= s.length() / 2; i++) {
            int length = compress(s, i);
            if (length < min) min = length;
        }

        return min == Integer.MAX_VALUE ? s.length() : min;
    }

    public static void main(String[] args) {
        String[] inputs = {
                "aabbaccc",
                "ababcdcdababcdcd",
                "abcabcdede",
                "abcabcabcabcdededededede",
                "xababcdcdababcdcd",
                "xxxxxxxxxxyyy",
                "a"
        };

        for (String s : inputs) {
            System.out.println(solution(s));
        }
    }
}

 

7
9
8
14
17
5
1

 

 추가적으로 고려해야 할 사항이 있었다. 문자열의 길이가 1인 경우 for 루프 자체를 돌지 않고 지나간다. 그렇기 때문에 최소값 min은 여전히 Integer.MAX_VALUE 이기 때문에 return 직전에 한 번 더 확인한다.

 

references.

소프트웨어공학과 이승진 교수님의 특강자료를 기반으로 작성된 게시글입니다.