[Programmers] 문자열 압축 (Java, Kotlin)

https://programmers.co.kr/learn/courses/30/lessons/60057

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

문제

입력값으로 문자열 s가 주어집니다. 문제에 주어진 비손실 압축 방법으로 짧은 문자열을 만들고자 할 때, 가장 짧은 문자열의 길이를 반환하는 문제입니다. 상세한 문제는 위의 페이지에서 확인 가능합니다.

 

접근 아이디어

1. 압축 단위를 1부터 입력 문자열 s의 길이까지 범위를 정합니다.

2. 압축 단위만큼 문자열 Index 0부터 자른 후에 다음 서브 문자열과 비교합니.

3. 압축이 가능한 부분은 count 변수를 이용하여 문자열을 재구성합니다.

4. 각 압축 단위마다 길이를 비교하여 최소 문자열 길이를 찾은 후에 반환합니다.

 

조심해야할 점

1. String에서의 Index를 참조할 때 범위를 잘 고려해야 합니다. 

2. Index 0 부터 N개를 자르는 상태로 압축이 가능한지 확인해야 합니다.

 

 

- Java

class Solution {
    
	public static int solution(String s) {
    
        int answer = Integer.MAX_VALUE;

        //압축 단위
        for (int i = 1; i < s.length(); i++) {

            String result = "";
            String str = "";
            String nextStr = "";
            int count = 1;

            //문자열 인덱스
            for (int j = 0; j < s.length(); j += i) {
                str = s.substring(j, j + i);
                if (j + 2 * i <= s.length()) {
                    nextStr = s.substring(j + i, j + 2 * i);
                } else {
                    nextStr = s.substring(j + i);
                }

                if (str.length() == nextStr.length()) {
                    if (str.equals(nextStr)) {
                        count++;
                    } else {
                        if (count != 1) result += count;
                        result += str;

                        count = 1;
                    }
                } else {
                    //마지막 종료 지점
                    if (count != 1) {
                        result += count;
                        count = 1;
                    }
                    result += (str + nextStr);
                    break;
                }

            }

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

            answer = Math.min(answer, result.length());
        }

        return answer == Integer.MAX_VALUE ? 1 : answer;
    }
}

 

 

- Kotlin

class Solution {

    fun solution(s: String): Int {
        var answer = Integer.MAX_VALUE;

        //압축 단위
        for (i in 1 until s.length) {
            var result = "";
            var str = "";
            var nextStr = "";
            var count = 1;

            //문자열 인덱스
            for (j in s.indices step i) {
                str = s.substring(j, j + i);
                if (j + 2 * i <= s.length) {
                    nextStr = s.substring(j + i, j + 2 * i);
                } else {
                    nextStr = s.substring(j + i);
                }

                if (str.length == nextStr.length) {
                    if (str.equals(nextStr)) {
                        count++;
                    } else {
                        if (count != 1) result += count;
                        result += str;

                        count = 1;
                    }
                } else {
                    //마지막 종료 지점
                    if (count != 1) {
                        result += count;
                        count = 1;
                    }
                    result += (str + nextStr);
                    break;
                }
            }

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

            answer = Math.min(answer, result.length);
        }

        return if(answer == Integer.MAX_VALUE) 1 else answer
    }
}

 

좌(Java 채점 결과), 우(Kotlin 채점 결과)