자바(JAVA) - 문자열 압축(Programmers : 60057)

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

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

카카오 코테를 준비하며 접한 문제,,
너무 긴장해서 그런가 문제가 잘 파악이 안되서 정확히 이해하기까지 시간이 많이 소요됐다..
어떤 알고리즘으로 어떻게 효율적으로 쪼갤지 고민을 참 많이하게 한 문제,,
하지만,, 모든 문제를 시원하게 해결해 준 결정적 힌트는 문제 맨 마지막, 5번 예제 설명에 있었다..
'문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.'
완전 탐색으로 왼쪽으로부터 각 길이만큼의 텍스트를 쪼개며 정답을 쉽게 구할 수 있었다.

 

실행 순서는 다음과 같다 :

    1. Outter For문으로 index 0 - i 까지의 substring 지정

    2. Inner For문으로 i 길이만큼씩 텍스트를 잘라가며 output 완성

    3. output의 길이와 answer 값중 더 작은 값으로 answer 갱신

    4. answer 반환

 

 

<코드>

class Solution {
    public int solution(String s) {
        int answer = 1000;
        
        if(s.length() < 2) {
            return s.length();
        }
        
        for(int i = 1; i < s.length() / 2 + 2 ; i++) {          
            // subStr 사이즈 : 압축사이즈
            String subStr = s.substring(0, i);
            String output = "";
            int count = 1;
            int lastIndex = 0;
            
            for(int j = i ; j + i <= s.length(); j += i) {
                // 비교 대상 String
                String strToCompare = s.substring(j, j + i);
                
                // 텍스트가 연속되어 압축 가능한 경우
                if(subStr.equals(strToCompare)) {
                    count++;
                // 연속되지 않는 경우
                } else {
                    if(count > 1) {
                        output += count;
                        count = 1;
                    }
                    output += subStr;
                    subStr = strToCompare;
                    
                }
                lastIndex = j + i;
            }
            
            // 마지막 round에서 기록된 값 업데이트
            if(count > 1)
                output += count;
            output += subStr;
            
            // String을 끝까지 확인하지 않고 끝난 경우
            if(lastIndex < s.length()) {
            	output += s.substring(lastIndex);
            }
            
            // 더 짧은 output 길이로 업데이트
            answer = Math.min(answer, output.length());
        }
        
        return answer;
    }
}