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

1. 문제

https://programmers.co.kr/learn/courses/30/lessons/60057?language=java 

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

 

2. 풀이

1. 문자열이 압축 되기 위해 가능한 길이의 최댓값은 (문자열 길이)/2 이므로, for문을 통해 1~(문자열 길이)/2까지 증가시키며 압축을 진행한다
   • 증가시키는 인덱스의 값이 압축되는 패턴의 길이다.
   • 압축을 진행한 결과 가장 길이가 짧은 값을 리턴한다.
2. 압축
   • for문으로, 이전의 패턴 문자열과 비교할 현재의 문자열(nowZip)을 정한다
     • i + len < s.length()면 패턴 길이만큼 자른다
     • 패턴 길이보다 작은 상황이면, 압축이 불가능하므로 진행하지 않는다.
   • 패턴이 없는 경우 == 맨 처음이 아닌 경우, 이전의 패턴과 현재의 문자열(nowStr)을 비교한다.
     • 패턴이 일치하면(nowZip.equals(nextZip)) 압축이 가능하므로, 압축 횟수를 의미하는 zipCnt 변수 값을 증가시킨다.
     • 패턴이 일치하지 않지만, 이전에 압축이 진행된 경우, 압축 횟수와 문자열을 더해 압축을 진행한다.

 

3. 코드

 

 

class Solution {
    public int solution(String s) {
        int answer = s.length();
        
        for(int l = 1; l <= s.length()/2; l++){
            int zipCnt = 1; // 압축 횟수
            String nowZip = s.substring(0, l); // 현재 압축한 문자열
            int nowLen = s.length(); // 현재 문자열 길이
            
            for(int i = l; i < s.length(); i += l){
                if(i+l > s.length()) continue; // 압축 불가능한 경우
                
                String nextZip = s.substring(i, i + l); // 다음 문자열
                if(nowZip.equals(nextZip)){ // 압축 가능
                    zipCnt++;
                }else{ // 압축 불가능
                    if(zipCnt != 1){
                        int numLen = String.valueOf(zipCnt).length();
                        nowLen = nowLen - l * (zipCnt - 1) + numLen;
                    }
                    zipCnt = 1;
                    nowZip = nextZip; // 다음 문자열이 압축할 문자열
                }
                
            }
            
            if(zipCnt != 1){
                int numLen = String.valueOf(zipCnt).length();
                nowLen = nowLen - l * (zipCnt - 1) + numLen;
            }
            
            answer = Math.min(answer, nowLen);
        }
        
        return answer;
    }
}