문자열 압축 - '2020 카카오 코딩 테스트'

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

문자열이 주어지고, 앞 문자열과 바로 뒷 문자열이 같은면, 같은 횟수 만큼의 숫자와 문자로, 문자열을 압축 하였을때, 문자열의 길이가 가장 작은 길이를 출력 하는 문제 입니다.

 

1. 접근

1. 문자열의 길이가 1000 이하 이므로, 완전 탐색으로 해결 할수 있을거 같습니다.

2. 압축 할 수 있는 최대 길이는 주어진 문자열의 반까지만 압축 할 수 있습니다.

3. 따라서 1부터 문자열의 반까지 완전 탐색 하면서 압축을 합니다.

4. 가장 짧은 문자열의 길이를 출력 합니다.

 

처음 시도 할때, 반복문과 재귀 함수를 같이 사용하면서, 헤매게 되어서, 소스코드를 지우고 다시, 구현 했습니다.

public class Page323_4 {
    public static void main(String[] args) {
        String s = "aabbaccc";
        System.out.print(new Page323_4().solution(s));
    }

    public String solution(String str) {
        String totalCompStr = str;
        int halfLen = str.length() / 2;

        // 1글자 압축 부터 halfLen 까지 순차 압축
        for (int compSize = 1; compSize <= halfLen; compSize++) {
            String compStr = "";
            String prevStr = str.substring(0, compSize);
            int cnt = 1;

            for (int i = compSize; i < str.length(); i += compSize) {
                String subStr = "";

                // subStr = str.substring(i, i + compSize);
                // 주의 위와 같이 subStr 을 구하면, compSize 길이 만큼
                // 딱 안떨어지는 문자열들은 담을 수 없다.
                for (int k = i; k < i + compSize; k++) {
                    if (k < str.length())
                        subStr += str.charAt(k);
                }

                if (prevStr.equals(subStr)){
                    cnt++;
                } else {
                    compStr += compress(prevStr, cnt);
                    prevStr = subStr;
                    cnt = 1;
                }
            }
            compStr += compress(prevStr, cnt);

            if (totalCompStr.length() > compStr.length())
                totalCompStr = compStr;
        }
        return totalCompStr;
    }

    private String compress(String prevStr, int cnt) {
        String compStr;
        if (cnt > 1)
            compStr = cnt + prevStr;
        else
            compStr = prevStr;
        return compStr;
    }
}

 반복문을 이용한 구현 입니다.

 

 

// subStr = str.substring(i, i + compSize);
// 주의 위와 같이 subStr 을 구하면, compSize 길이 만큼
// 딱 안떨어지는 문자열들은 담을 수 없다.
for (int k = i; k < i + compSize; k++) {
	if (k < str.length())
		subStr += str.charAt(k);
}

위 소스 코드에서 헤매었습니다. str.substring()으로 위 반복문을 대체 할수 있을거라고 생각 했는데, 결과는 다르게 나왔습니다. 디버깅을 해보며 알수 있었습니다. compSize가 나머지 문자열의 길이 보다 큰 경우 substring() 으로는 subStr을 담을 수 없었습니다.

 

 

compStr += compress(prevStr, cnt);

또한, 이 부분을 재귀 함수로 빼려다 보니, 애를 먹었었습니다. 결국 이 부분은 빼지 않고 반복문으로 구현 하였습니다.

 

 

public class Page323_6 {
    public static void main(String[] args) {
        String s = "aabbaccc";
        System.out.print(new Page323_6().solution(s));
    }

    public int solution(String s){
        int halfLen = s.length() / 2;
        int answer = Integer.MAX_VALUE;

        // i는 압축할 문자열 길이
        for (int i = 1; i <= halfLen; i++) {
            String str = compressStr(s, i, 1);
            answer = answer > str.length() ? str.length() : answer;
        }
        return answer;
    }

    private String compressStr(String s, int compSize, int repeat) {
        // 압축 사이즈 보다 작으면, 문자열 그대로 리턴
        if (s.length() < compSize) return s;
        String prevStr = s.substring(0, compSize);
        String postStr = s.substring(compSize);

        // 같지 않다면, 현재까지 문자열 + 반복 횟수 + 압축 문자 + 나머지 문자열
        if (!postStr.startsWith(prevStr)) {
            if (repeat == 1)
                return prevStr + compressStr(postStr, compSize, 1);
            else
                return repeat + prevStr + compressStr(postStr, compSize, 1);
        }

        return compressStr(postStr, compSize, repeat + 1);
    }
}

 

다른 분의 소스코드중 재귀 함수로 구현 하신분의 소스 코드 입니다. 1부터 문자열의 길이의 반까지 완전 탐색으로 압축을 시도 하였고, 현재 까지 문자열 + 반복 횟수 + 압축 문자열 + 나머지 문자열을 분리 하여, 재귀 함수로 구현 하였습니다. 또한 compSize 보다 문자열의 길이가 작을 때는, 문자열을 전부 반환하는 수렴 조건(Base Case)가 구현 되어 있습니다.