2020 - 문자열 압축

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

코딩테스트 연습 - 문자열 압축

[ 문제풀이 ]

주어진 문자열을 1부터 문자열의 절반까지 압축하여 최소 길이를 찾으면 되는 문제이다.

​주의해야 할 점은 압축하는 위치?이다. 입출력 예 #5를 보면 알겠지만 압축은 무조건 제일 앞에서 압축할 길이만큼씩 진행한다.

​또한, 문자열의 최대 길이가 1000이기 때문에 중복된 횟수는 1~1000까지 나타날 수 있다. 따라서 중복된 횟수에 따라 나눠서 압축해줘야 한다.

class Solution {
	public int solution(String s) {
		int answer = s.length();

		//s의 절반까지만 압축 가능
		for (int unit = 1; unit <= s.length() / 2; ++unit) {
			int strlen = s.length();
			int cnt = 0;
			String before = s.substring(0, unit);
			
			for (int i = unit; i + unit <= s.length(); i += unit) {
                //비교해야할 문자열을 추출
				String now = (i == s.length() - unit) ? s.substring(i) : s.substring(i, i + unit);
				
				//이전의 문자열과 같으면 cnt 증가
				if (before.equals(now)) {
					cnt++;
				} 
				//다르다면 이전의 문자열을 변경해주고 압축
				else {
					before = s.substring(i, i + unit);
					strlen = calc(unit, cnt, strlen);
					cnt = 0;
				}
			}

			//cnt가 남아있으면 마지막으로 압축
			strlen = calc(unit, cnt, strlen);

			answer = Math.min(answer, strlen);
		}
		return answer;
	}

	public int calc(int unit, int cnt, int strlen) {
		if (cnt == 0) return strlen;

		//중복된 횟수 빼줌
		strlen -= cnt * unit;
		//횟수가 1, 10, 100, 1000의 자리일 경우 처리 
		strlen += (int) Math.log10(cnt + 1) + 1;
		return strlen;
	}
}