[프로그래머스] 문자열 압축

문제 URL

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

풀이

해당 문제는 제한사항이 s의길이가 1이상 1000이하이므로 복잡도가 O(n제곱)인 브루트포스로 풀었다.

for문을 이용한 풀이는 1) 1부터 s.length/2까지 1씩 증가하면서 문자를 자르는 단위를 정해야한다. 2) 자르는 단위를 정했으면 문자열 시작점 0부터 기준점을잡고 각각 문자열 단위마다 문자열 중복이 있는지 검사를시작한다.

나의 풀이

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

        //i = 문자를 자르는 단위
        for (int i = 1; i <= s.length()/2; i++) {
            int len = 0;
            StringBuilder sb = new StringBuilder();
            // 문자열 시작점 0 부터 단위 i만큼 증가
            for(int j=0; j<s.length(); j+=i){
                String base;
                if(j+i < s.length()){
                    base = s.substring(j, j+i);
                }else{
                    base = s.substring(j);
                }
                int dup = 1;

                // 중복 검사
                for(int k=j+i; k<s.length(); k+=i){
                    String compare;
                    if(k+i<s.length()){
                        compare = s.substring(k, k+i);
                    }else{
                        compare = s.substring(k);
                    }
                    if(!compare.equals(base))
                        break;
                    dup++;
                    j=k;
                }


                if(dup>1){
                    sb.append(dup+base);
                }else{
                    sb.append(base);
                }
            }
            if(answer>sb.length()) {
                answer = sb.length();
            }
        }

        return answer;
    }
}

다른 풀이

by 송동훈 , choiyeonseok (programmers)

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

        for(int i=1; i<=(s.length()/2)+1; i++){
            int result = getSplitedLength(s, i, 1).length();
            answer = i==1 ? result : (answer>result?result:answer);
        }

        return answer;
    }

    public String getSplitedLength(String s, int n, int repeat){
        if(s.length() < n) return s;
        String result = "";
        String preString = s.substring(0, n);
        String postString = s.substring(n, s.length());

        // 불일치 -> 현재까지 [반복횟수 + 반복문자] 조합
        if(!postString.startsWith(preString)){
            if(repeat ==1) return result += preString + getSplitedLength(postString, n, 1);
            return result += Integer.toString(repeat) + preString + getSplitedLength(postString, n, 1);
        }

        return result += getSplitedLength(postString, n, repeat+1);
    }
}