[Programmers] 문자열 압축

2020 Kakao Blind Recruitment

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

---

[문자열]

백준에 길들여지고, 카카오의 효율성 문제에 길들여진 나머지, 문자를 쪼개어 비교하는 것은 생각하지도 않았었다. 이는 간단하지만 시간이 상당히 오래 걸리는 작업이기 때문이다. 그래서 굳이 돌고돌아 조금더 어려운 방법이지만 빠른 방법이 뭐가 있을까 하다가 배열 스택을 생각해냈고, 이를 적용해 풀어보다가 도저히 아닌 거 같아 몇몇 게시글을 찾아보니 문자열을 쪼개 비교하는 것이 아닌가.

 

그래서 작성한 코드를 모두 지우고 다음과 같이 작성했다.

 

1. 주어진 문자열의 길이가 n이라면 문자열을 1개 ~ n/2개로 쪼갰을 때 압축한 문자열의 길이를 구한다.

(n/2개 까지 하는 이유는 그 이상의 개수로 문자열을 쪼개면 반복을 1개도 찾을 수 없기 때문이다.)

 

2. 나는 문자열을 쪼개 결과 문자열에 숫자와 문자열을 덧붙이고, 최종적으로 그 문자열의 길이를 구하는 방식으로 하지 않았다.

문자열을 덧붙이는 대신, 붙여질 문자열의 길이와 숫자의 자릿수를 더하는 식으로 했다.

# Code </>

class Solution {

    public int solution(String s) {

        int n = s.length();
        int min = n;
        
        for(int i=1; i<=n/2; i++){

            int count = 1;
            int result = 0;
            String piece = s.substring(0, i);
            String nextPiece;

            for(int j=i; j<n; j += i){

                if(j + i < n)
                    nextPiece = s.substring(j, j+i);
                else
                    nextPiece = s.substring(j);

                if(piece.equals(nextPiece)) count++;
                else{
                    if(count > 1) result += String.valueOf(count).length(); //2, 3, 4, ... 12 같은 수의 자릿수
                    result += nextPiece.length(); //쪼개진 문자열의 길이

                    piece = nextPiece;
                    count = 1;
                }
            }
            if(count > 1) result += String.valueOf(count).length();
            result += i;

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

        return min;
    }
}