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

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

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

문제 요약 

N자릿수의 문자열이 있을 때 반복되는 문자열은 반복되는 횟수 + 문자열로 나타내려 하는데

몇자리로 압축을 했을 때 가장 짧은 문자열이 되는지를 구하는 문제.

 

예를 들어 aaabb라는 문자열이 있을 때

1자리로 압축하면 3a2b

2자리로 압축하면 aaabb

로 한자리로 압축했을 때 4자리가 가장 짧음으로 답은 4가 된다.

 

풀이 방법

일단.. 꼼꼼함이 부족하다는 생각을 많이 하게된 문제다.

로직은 단순히 2중 반복문을 돌리면 되는데

if else조건으로 경우의 수를 나누는 부분에서 여러가지를 고려해야 했다.

 

우선

1. 몇자리까지 압축할 수 있는지?

2. 문자열은 10자린데 3자리로 압축할 때 마지막 문자가 남는데 어떻게 처리 할건지?

등등 풀면 풀수록 구멍이 숭숭나서 매꾸느라 시간이 좀 걸렸다.

나머지 포인트는 주석에 첨부했다.

 

import java.util.ArrayList;

class Solution
{
    public int solution(String s) {
        int answer = s.length();
        int length = s.length();    //문자열의 길이
        int repeatable = length/2;  //몇자리까지 압축 가능한지

        for(int i =1 ; i <= repeatable; i++){ // 몇자리로 자를지 
            int cnt = 1; //반복횟수 저장 변수
            int minLength = 0; //압축한 문자열의 길이
            for(int j = 0; j+2*i <= length; j+=i){ //문자열 스캔을 위한 for loop
                String subStr = s.substring(j, j+i);       //대상 문자열
                String compareStr = s.substring(j+i, j+2*i);    //비교문자열
                if(!subStr.equals(compareStr)){ //같은지 비교
                    if(cnt > 1){    //이번 비교에선 문자가 같지 않지만, 이전 문자들은 반복되어 cnt가 1초과인 경우
                         minLength += String.valueOf(cnt).length(); //반복된 횟수 변수의 자릿수를 더해주고
                         minLength += i;    //반복된 문자열의 길이를 더해준다.
                         cnt = 1;   //반복 횟수는 1로 초기화 한다.
                    }else{
                        minLength += i; //반복된 히스토리도 없고 반복되지도 않았을 때 대상 문자열의 길이만 더해준다.
                    }
                }else{  //문자열이 일치하다면, 반복횟수만 올려주고 continue
                    cnt++;
                }
            }
            //예를 들어 10자리 문자열에 3자리로 압축을 할 경우 나머지 1자리는 비교의 기회도 없기 반복문이 종료되는데
            //이 경우 나머지 자릿수를 더해줌으로 써 문자열 길이를 계산한다. 
            if(length%i !=0){
                minLength += length%i;
            }
            //마지막까지 반복되다 끝난경우 
            //최종적으로 결과에 반영이 되지 않음으로 여기서 반해준다.
            if(cnt > 1){
                minLength += String.valueOf(cnt).length();
            }
            minLength += i;
            //이전보다 압축된 문자열의 길이가 짧다면 이를 반영한다.
            if(minLength < answer){
                answer = minLength;
            }
        }
        return answer;
    }
}