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

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

접근 방법

1부터 문자열의 반틈 길이만큼 잘라서 압축한다(완전 탐색)

길이 1일때의 압축 길이
길이 2일때의 압축 길이
...
길이 s.length() / 2일때의 압축 길이
이를 모두 비교하면서 가장 작은 값을 구한다.

s의 최대 길이가 1000이고, 시간 복잡도는 O(s^2) 이기에 완전 탐색에 무리가 없다.

앞의 글자를 차례대로 압축하는 것이기 때문에, 큐를 만들어 하나씩 뽑아서 진행했다.

소스 코드

import java.util.*;

class Solution {
    public int solution(String s) {
        if(s.length() == 1){
            return 1;
        }
        
        int answer = 100000;
        for(int len=1;len<=s.length()/2;len++){
            ArrayList<String> list = new ArrayList<>();

            // 분할
            int start = 0;
            boolean stop = false;
            while(!stop){
                int end = start + len;
                if(end >= s.length()){
                    end = s.length();
                    stop = true;
                }
                String str = s.substring(start, end);
                list.add(str);
                start += len;
            }

            // 큐에 넣고 앞글자부터 순서대로 압축 진행
            Queue<String> queue = new LinkedList<>(list);
            String previous = queue.poll();
            String now = null;
            int count = 1;
            int length = 0;
            int numLength = 0;
            while(!queue.isEmpty()){
                now = queue.poll();
                // 다음 문자가 현재 문자랑 같다면 압축
                if(now.equals(previous)){
                    count++;
                } else{ // 다르다면 길이 추가 및 타켓 변경
                    numLength = count == 1 ? 0 : String.valueOf(count).length();
                    length += previous.length() + numLength;
                    count = 1;
                }
                previous = now;
            }

            numLength = count == 1 ? 0 : String.valueOf(count).length();
            length += previous.length() + numLength;
            
            if(answer > length){
                answer = length;
            }
        }

        return answer;
    }
}