2020 카카오 1차 코딩테스트 문제 1

문제 해설

 

전체 코드

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

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

        for (int i = 1; i <= s.length() / 2; i++) {
            String result = compression(i, s);
            if (answer > result.length()) {
                answer = result.length();
            }
        }

        return answer;
    }
    
    // 압축된 문자열 만들기
    private String compression(int size, String s) {
        List<String> subStrings = getSubString(size, s);

        String result = "";
        String temp = subStrings.get(0);
        int count = 1;

        for (int i = 1; i < subStrings.size(); i++) {
            if (temp.equals(subStrings.get(i))) {
                count++;
            } else {
                result += addSubResult(count, temp);

                count = 1;
                temp = subStrings.get(i);
            }
        }

        result += addSubResult(count, temp);

        return result;
    }

    private String addSubResult(int count, String temp) {
        String result = "";

        if (count != 1) {
            result += count;
        }

        result += temp;

        return result;
    }
    
    // size 크기로 문자열 나누기
    private List<String> getSubString(int size, String s) {
        List<String> subStrings = new ArrayList<>();

        for (int i = 0; i < s.length() / size; i++) {
            subStrings.add(s.substring(i * size, (i + 1) * size));
        }
        // 나머지 넣기
        if (s.length() % size != 0) {
            subStrings.add(s.substring(s.length() - s.length() % size));
        }

        return subStrings;
    }
}

문자열 합

문제에서 압축된 가장 작은 문자열의 길이만 원한다.

 

문자열을 만들어서 합치는 거보다 합친 문자열의 길이만 구하는 게 속도가 더 빠르다. (문자열 합치는데 비용이 크기 때문에)

 

    private int compressionSize(int size, String s) {
        List<String> subStrings = getSubString(size, s);

        int result = 0;
        String temp = subStrings.get(0);
        int count = 1;

        for (int i = 1; i < subStrings.size(); i++) {
            if (temp.equals(subStrings.get(i))) {
                count++;
            } else {
                result += addSubResultSize(count, temp);

                count = 1;
                temp = subStrings.get(i);
            }
        }

        result += addSubResultSize(count, temp);

        return result;
    }

    private int addSubResultSize(int count, String temp) {
        if (count == 1) {
            return temp.length();
        }
        // (int)(Math.log10(count)+1) >> count 숫자의 자리수
        return temp.length() + (int)(Math.log10(count)+1);
    }

다른 부분은 같고 압축된 문자열의 길이를 구하도록 했다.

문자열 길이

 속도가 5배 이상 빨라진 것을 확인할 수 있다.