[프로그래머스 60057] Lv.2 문자열 압축

문제 Link

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

프로그래머스

 

문제풀이 Key Point

• 앞에서부터 일정한 간격으로 문자열을 잘랐을 경우, 최대한 많은 문자를 합치는 방법을 찾아야한다.
• 문자열을 자르는 범위는 문자열 길이의 절반 크기만큼만 확인하면 된다.
  • e.g.) aabbccdd 문자열을 자른다 했을때 길이 4를 넘는 5, 6, 7, 8...의 길이로 자르는 것은 불가능하다.
• 잘린 문자열이 x이면서 같은 갯수가 199개라면 199x이므로 압축된 길이는 4가 된다.

 

Java 풀이

import java.util.Queue;
import java.util.LinkedList;
 
class Solution {
    public int solution(String s) {
        int answer = s.length();
        
        Queue<String> queue = new LinkedList<>();
        for (int splitLength = 1; splitLength < s.length() / 2 + 1; splitLength++) {
            queue = splitStringAtRegularIntervals(s, splitLength);
            
            int sameCount = 1;
            int count = 0;
            while (!queue.isEmpty()) {
                String front = queue.poll();
                if (queue.isEmpty() || !isSameElement(queue, front)) {
                    count = findLengthOfTheConcatenatedString(sameCount, count, front.length());
                    sameCount = 1;
                } else if (isSameElement(queue, front)) {
                    sameCount++;
                }
            }
 
            if (answer > count) {
                answer = count;
            }
        }
        return answer;
    }
    
    private boolean isSameElement(Queue<String> queue, String front) {
        return front.equals(queue.peek());
    }
    
    private int findLengthOfTheConcatenatedString(int sameCount, int count, int length) {
        if (sameCount == 1) {
            count += length;
        } else {
            count = count + length + (String.valueOf(sameCount).length());
        }
        
        return count;
    }
    
    private Queue<String> splitStringAtRegularIntervals(String value, int splitLength) {
        Queue<String> queue = new LinkedList<>();
        for (int startIndex = 0; startIndex < value.length(); startIndex += splitLength) {
            if (startIndex + splitLength > value.length()) {
                queue.add(value.substring(startIndex));
            } else {
                queue.add(value.substring(startIndex, startIndex + splitLength));
            }
        }
        
        return queue;
    }
}