프로그래머스 레벨2 문자열 압축

문자열 압축

알고리즘 풀이
1. 가능한 모든 문자열의 조합을 찾아야되는줄 알고 문자열 조합만들고, ArrayList.contains() 써서 중복 제거할려하고 여러가지 고생을 함
substring(s, t) 계산하고, substring(s, length())해서 s부터 시작하는 문자열 다시 만들고 replace(sub, "#")해서 # 개수 찾고 이런 수고를 함

-> 이렇게 하니까 "xababcdcdababcdcd" 테스트케이스가 x2ababcdcd로 되서 오답이 나왔던걸로 기억함. 다시 문제보고 잘못 계산했다는걸 깨닮음

2. for 한번만 돌아서 맨 앞에서부터 (0, i)로 만든 substring을 #으로 바꾸고 #이면서 i, i+1이 같은 걸 찾고, 아니면 break 이런식으로 하다보니까 ##asdbeqwe## 일때 마지막 ##를 못찾는 경우가 발생

3. ##asdfsa## 이런걸 다 계산해줬는데도 케이스 몇개가 계속 실패남
   -> 3ab에서 숫자각 생기는걸 항상 +1로 해줬는데 100ab일 경우를 생각못함 (Math.log10()) 으로 해결함.

import java.util.Collections;
import java.util.ArrayList;
import java.lang.Math;

class Solution {
    public int solution(String s) {
        int answer = 0;
        ArrayList<Integer> ans = new ArrayList<>();
        
        // 문자열 개수
        for(int i = 1; i <= s.length(); i++)
        {
            int total = s.length();
            int cnt = 0;
            int st;
            for(st = 0; st + 2 * i <= s.length(); st += i)
            {
                if(s.substring(st, st+i).equals(s.substring(st + i, st + 2*i)))
                    cnt++;
                else
                    if(cnt > 0){
                        total = total - (i * cnt) + ((int)Math.log10(cnt+1) + 1);
                        cnt = 0;
                    }
            }
            if(cnt > 0)
                total = total - (i * cnt) + ((int)Math.log10(cnt+1) + 1);
            ans.add(total);
        }
        Collections.sort(ans);
        
        if(ans.isEmpty())
            answer = s.length();
        else
            answer = ans.get(0);
        
        return answer;
    }
}