Programmers - 문자열 압축(Java)

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

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

 

풀이

같은 값이 연속해서 나타나는 경우 반복되는 갯수를 표기하며 줄여서 표기 ex) aaa -> 3a 

* 단, 정해진 길이가 반복되는 경우만 압축가능 ex) aabbb -> 2a3b(X) -> 2a2bb(O)

 

* 완전 탐색으로 가장 작은 길이의 결과를 구하되, 탐색의 범위를 줄이는 것이 필요

주어지는 문자열의 길이를 이용하여 최대 압축 길이를 구함, 이 때 최대 압축 길이는 압축 할 수 있는 최대의 단위 길이

  ex) abacs라는 5의 길이를 가진 문자열은 3이상의 길이를 가진 문자로는 압축 불가

 

최대 압축 길이는 문자열 길이/2(소수점 내림) +1로 구할 수 있다.

 

1 ~ 최대 압축길이까지 압축 단위 길이 별로 탐색하여 문자를 압축하며 확인, 가장 적은 길이를 가진 문자열을 탐색

class Solution {
    public int solution(String s) {
        int answer = 1000;
        int len = s.length();
        
        // 길이가 1이라면 탐색의 필요 X
        if(len==1){
            return 1;
        }
        
        // 1~최대 압축 길이까지의 기준으로 문자열 압축
        for(int split=1; split<len/2 + 1; split++){
            String str = new String();
            // 0 ~ 압축 길이 만큼의 문자열 분리 
            String comp = s.substring(0, split);
            int cnt=1;
            
            for(int i=split;i<len;i+=split){
            	// 현재 탐색의 분리 문자열이 초기 문자열의 길이를 넘어간다면
                if(i+split>len){
                    // 이전 까지의 비교를 결과에 포함
                    if(cnt>1)
                        str+=cnt+comp;
                    else
                        str+=comp;
                    // 현재 부터 남은 문자열을 끝에 추가
                    comp = s.substring(i);
                    cnt=1;
                    continue;
                }
                // 현재(i~split)의 문자열과 비교 문자열 비교
                else if(comp.equals(s.substring(i, i+split)))
                    cnt++;
                
                else{
                    if(cnt>1)
                        str+=cnt+comp;
                    else
                        str+=comp;
                    comp = s.substring(i, i+split);
                    cnt=1;
                }
            }
            
            if(cnt>1)
                str+=cnt+comp;
            else
                str+=comp;
            
            // 최소 길이 결과 갱신
            if(answer>str.length()){
                answer=str.length();
            }
        }
        return answer;
    }
}