[Programmers/60057/JAVA] 문자열 압축

날짜	분류	번호	알고리즘 분류
21-03-25	프로그래머스	60057	문자열	링크

문제 요약

1. 문자열을 앞에서부터 n개씩 잘랐을 때 같은 값이 연속해서 나오면 반복해서 나온 개수``반복된문자열로 줄인다
   • ex) ababrtrt => 2ab2rt
2. n개씩 자르고 남은 문자열은 뒤에 붙여줌
3. 압축한 후의 길이를 비교해서 가장 짧은 것을 정답으로 반환

 

풀이

1. 길이를 1~문자열의길이 반복
2. idx를 0부터 길이만큼 늘려주면서 반복
3. 이전 문자열과 지금 문자열을 비교해서 같으면 cnt 증가
   • 다르면 String builder인 result에 cnt와 직전 문자열을 붙여줌
   • cnt가 1이면 붙이지 않음
   • pre=cur을 해주고, cnt는 1로에 초기화
4. 남은 문자열 털어넣기
5. 비교

 

비고

• 테케 5번이 하나 틀렸는데.... 바로바로,,, length가 1인 문자열....! 두둥탁
  • 시간 좀 줄여보겠다고 자르는 단위를 1부터 lenth/2로 했더니 위의 테케를 틀림... ㅠㅠ

 

package KakaoBlindRecruitment2021.P60057_문자열압축;

public class Solution {

	static int solution(String s) {
		int answer = Integer.MAX_VALUE;

		for (int len = 1; len <= s.length(); len++) {
			int idx = 0;
			int cnt = 1;
			String pre = "";
			String cur = "";
			StringBuilder result = new StringBuilder();
            
			while (idx + len <= s.length()) {
				cur = s.substring(idx, idx + len);

				if (pre.equals(cur)) {
					cnt++;
				} else {
					if (cnt > 1)
						result.append(cnt);
					result.append(pre);

					cnt = 1;
					pre = cur;
				}

				idx += len;
			}
            
			if (cnt > 1)
				result.append(cnt);
			result.append(pre);
            
			if (idx < s.length())
				result.append(s.substring(idx));
                
			answer = Math.min(answer, result.length());
		}

		return answer;
	}

	public static void main(String[] args) {
		System.out.println(solution("aabbaccc"));
		System.out.println(solution("ababcdcdababcdcd"));
		System.out.println(solution("abcabcdede"));
		System.out.println(solution("abcabcabcabcdededededede"));
		System.out.println(solution("xababcdcdababcdcd"));
	}

}