[프로그래머스 level 2] 문자열압축 - Java

문제

데이터 처리 전문가가 되고 싶은 "어피치"는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

 

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

 

문제풀이

• 문자의 최대 압축 길이를 구하기 위해서 먼저, 특정 문자를 대상으로 압축 가능한 모든 경우의 수를 구했다.
• 가령 길이가 10인 문자열이라면 1~5의 길이로 잘랐을 때 문자열을 압축할 수 있는 조건을 갖는다.
• 각각의 모든 경우의 수를 검토하며 문자열 압축 결과가 가장 좋은 것을 답으로 제출한다.

 

문자열 압축 알고리즘

• 아래의 compressResolver 메소드는 특정 문자열과 문자열을 자르는 길이가 인자로 주어졌을 때 작동한다.
• compressResolver의 메커니즘은 다음과 같다.
• 가장 먼저 문자열을 특정한 길이로 쪼개 ArrayList에 하나하나 담는다.
• ArrayList에 들어 있는 값을 앞에서부터 두 개 가져와 서로 비교한다. 만약 비교한 두 값이 서로 같다면 count의 값만을 하나 올리고, 같지 않다면 앞의 문자열과 count 값을 result에 반영한다. (만약 count가 1이라면 count 값은 생략)
• 이 과정은 비교하고자 하는 값들이 ArrayList의 마지막 두 값일 때까지 반복된다.
• 만약 비교하고자 하는 값들이 마지막 두 값에 도달한다면, 두 값을 count의 상황에 맞게 result에 반영하고 반복 작업을 중단한다.
• result에 문자열을 자르고 남은 잔류 문자열을 더해 압축 결과로 반환한다.

 

import java.util.ArrayList;
import java.util.List;

public class StringCompression {

    public int solution(String s) {
        int MIN_DIVISION = 1;
        int MAX_DIVISION = s.length() / 2;
        return getMaxCompression(s, MIN_DIVISION, MAX_DIVISION);
    }

    private int getMaxCompression(String s, int MIN_DIVISION, int MAX_DIVISION) {
        int result = s.length();
        for (int currentDivision = MIN_DIVISION; currentDivision <= MAX_DIVISION; currentDivision++) {
            String representative = s;
            int compressed = compressResolver(currentDivision, representative);

            if (compressed < result) {
                result = compressed;
            }
        }
        return result;
    }

    public int compressResolver(int division, String target) {
        List<String> list = new ArrayList<>();
        while (target.length() >= division) {
            list.add(target.substring(0, division));
            target = target.substring(division);
        }

        int result = 0;
        int count = 1;
        for (int i = 1; i < list.size(); i++) {
            String compareA = list.get(i - 1);
            String compareB = list.get(i);

            if (compareA.equals(compareB)) {
                count++;
            } else {
                if (count == 1) {
                    result += division;
                } else {
                    result += String.valueOf(count).length() + division;
                    count = 1;
                }
            }
            if (i == list.size() - 1) {
                if (count != 1) {
                    result += String.valueOf(count).length() + division;
                } else {
                    result += division;
                }
            }
        }
        return result + target.length();
    }
}

 

 

느낀 점

이 문제를 풀려고 3일을 붙잡고 있었다. 코드를 짜놓고 정답을 제출하면, 고려하지 못했던 부분에서 오답이 나오고, 또 그 오답을 반영하기 위해 예외적인 경우를 코드에 적어놓으면, 그 코드 때문에 다른 문제가 틀려 버리는, 그래서 결국에는 코드가 어마어마하게 지저분해지는 그런... 경험을 했다. 코드가 막 100줄 가까이 되려는데 중간 중간 if문 if else문이 너무 많아서 코드를 읽을 수도 없는 그런 지경.. 

 

결국 코드를 다 지우고 나서 곰곰히 원리를 고민한 후에 다시 새로 코드를 만드니 위와 같은 코드가 나왔다. 100줄에서 절반이나 줄어든 50줄의 코드이지만 정확성은 비교할 수 없이 좋은 코드. 

 

코드를 짤 때, 단순히 생각이 가는대로 하기보다는 계획을 세우고 어느정도 방향성을 설계한 후에 접근하는게 훨씬 좋다는 걸 알게 됐다.

 

3일이라니...... 흐하.......