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

프로그래머스 문자열 압축

문제풀이

완전탐색 문제로 구현에 조금 신경을 쓰면 쉽게 풀 수 있는 문제였다. String 비교로 구현하면 시간초과가 나지 않을까 걱정하여 다른 방법을 열심히 생각해봤지만 모두 구현이 어렵거나 더 오래걸릴 것 같아서 String 비교로 구현을 했는데 다행이 통과했다.

구현코드

class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        
        for(int len = 1 ; len < s.length() ; ++len){            
            String compressed = "";
            String target = "";
            String current = "";
            int cnt = 1;
            
            // 첫 번쨰 단위 지정
            for(int i = 0 ; i < len ; ++i) {
            	target += s.charAt(i);
            }
            
            // 단위만큼 잘랐을 때 각 부분의 시작 인덱스
            for(int i = len ; i < s.length() ; i += len){
                current = "";
                for(int j = i ; j < i + len ; ++j){
                	if(j >= s.length()) break;
                    current += s.charAt(j);
                }
                
                if(target.equals(current)){
                    cnt++;
                } else {
                    if(cnt > 1){
                        compressed += cnt + target;
                    } else {
                        compressed += target;
                    }
                    cnt = 1;
                    target = current;
                }
            }
            
            if(cnt > 1){
                compressed += cnt + target;
            } else {
                compressed += target;
            }
            
            int length = compressed.length();
            answer = answer > length ? length : answer;
        }
        
        if(answer == Integer.MAX_VALUE) answer = 1;
        
        return answer;
    }
}