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

문제 풀이

문제 설명은 해당 링크를 참조하자.

쪼개는 문자 개수 단위를 1 ~ n / 2 까지로 설정하여 쪼개서 압축한 다음 각각의 문자열 길이를 세면 된다. 여기서 문자열 길이가 1인 경우 1/2 = 0이기 때문에 쪼갤 수가 없으니 따로 값을 반환해야 하므로 주의하자.

import java.util.ArrayList;

class Solution {
    public int counter(String s, int unitLength){
    // 쪼개는 문자 개수 단위를 설정하여 쪼개서 압축
        StringBuilder sb = new StringBuilder(s);
        ArrayList<String> subStringList = new ArrayList<>();
        ArrayList<Integer> countList = new ArrayList<>();
        // subStringList[i]가 연속으로 나오는 횟수가 countList[i]가 되도록 함

        while(sb.length() != 0){
            String subString = 
                sb.substring(0, Math.min(unitLength, sb.length()));
            sb.delete(0, Math.min(unitLength, sb.length()));

            if(!countList.isEmpty() && 
            subStringList.get(countList.size() - 1).equals(subString)){
                int temp = countList.get(countList.size() - 1);
                countList.remove(countList.size() - 1);
                countList.add(temp + 1);
                // 부분 문자열 개수 1 증가시킴
            } else{
                subStringList.add(subString);
                countList.add(1);
                // 부분 문자열이 처음 나오는 경우 1로 설정
            }
        }

        StringBuilder result = new StringBuilder();

        for(int i = 0;i < countList.size();i++){
            int count = countList.get(i);
            if(count != 1) result.append(count);

            result.append(subStringList.get(i));
        }

        return result.length();
    }

    public int solution(String s) {
        if(s.length() == 1) return 1;
        int min = 1000;
        for(int length = 1;length <= s.length() / 2;length++){
            min = Math.min(min, counter(s, length));
            // 최소 길이 업데이트
        }

        return min;
    }
}