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

• 문제 링크 : 문자열 압축

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

 

정답

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

        for(int i=1; i<=len/2; i++){
            String str1 = s.substring(0, i);
            int cnt = 1;
            int min = 0;

            for(int j=i; j<=len; j+=i){
                String str2 = s.substring(j, j+i > len ? len : j+i);
                if(str1.equals(str2)){
                    cnt++;
                }else{
                    min += str1.length();
                    if(cnt > 1){
                        min += (int)Math.log10(cnt) + 1;
                    }
                    str1 = str2;
                    cnt = 1;
                }
            }

            min += str1.length();
            if(cnt > 1){
                min += (int)Math.log10(cnt) + 1;
            }
            answer = Math.min(answer, min);
        }

        return answer;
    }
}

 

분석

• 문자열 다루기 문제

//end index에 3항 연산자를 사용하여 아웃바운드 방지
String str2 = s.substring(j, j+i > len ? len : j+i);

• 중복된 숫자가 2자리 이상이 되는 경우를 생각하지 않음
  • 단순 cnt > 1인 경우 +1을 해주어 실패가 발생함

  //cnt > 1 -> min++; 하면 아래의 경우 실패
  
  "aaaaaaaaaaaabcd" -> "12abcd" 이므로 6 자리
  
  "xxxxxxxxxxyyy" -> "10x3y" 이므로 5 자리 

 

계속 제출에서 실패한 코드

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

        for(int i=1; i<=len/2; i++){
            String str1 = s.substring(0, i);
            int cnt = 1;
            int min = 0;

            for(int j=i; j<=len; j+=i){
                String str2 = s.substring(j, j+i > len ? len : j+i);
                if(str1.equals(str2)){
                    cnt++;
                }else{
                    min += str1.length();
                    if(cnt > 1){
                        min++; //실패 원인
                    }
                    str1 = str2;
                    cnt = 1;
                }
            }

            min += str1.length();
            if(cnt > 1){
                min++; //실패 원인
            }
            answer = Math.min(answer, min);
        }

        return answer;
    }
}