[Programmers] 문자열 압축 - 2020 카카오공채

import java.util.ArrayList;

// 문자열 압축 - 2020 카카오공채
public class StringCompression {

	public int solution(String s) {

		ArrayList<String> list = new ArrayList<String>(); // 문자열 s 를 1, 2, ... 크기로 잘려진 토막을 넣을 리스트.
		String str = ""; // 리스트에 넣을 토막 
		String temp = ""; // 문자열을 압축한 결과를 저장하는 변수
		
		int min = s.length(); // 압축한 문자열의 길이의 최솟값을 저장. 최솟값은 문자열 s의 길이를 넘지 않음
		int count = 1; // 반복되는 토막의 갯수 카운트
		int i = 0, j = 1;

		if (s.length() == 1) { // 문자열 s 가 예를 들어 'a' 와 같이 한 글자일때 처리.
			return 1;
		}

		while (true) {

			int k = i + j;
			if (k > s.length()) { // k 가 s의 길이보다 넘어갈 시 처리해줌. ex) s = "abcabcdede' 일때 3글자로 자른다면 'abc' 'abc' 'ded' 'e??' 로 잘라지기 때문에 배열범위 초과 예외가 발생한다. 따라서 'abc' 'abc' 'ded' 'e' 로 잘리도록 처리.
				k = s.length();
			}
			str = s.substring(i, k); // 1 부터 s의 길이의 절반 크기까지로 자름 
			list.add(str); // 토막을 리스트에 저장
			i += j; // i 는 j의 크기 만큼 증가하여야 한다. 예를들어 j가 2일 때, 0-2 2-4 4-6 이런식으로 토막이 나야함
			if (i >= s.length()) {

				for (int h = 1; h < list.size(); h++) {

					if (list.get(h - 1).equals(list.get(h))) { // 이전 토막과 현재 토막이 같다면 카운트를 증가
						count++;
					} else {
						if (count == 1) { // 카운트가 1 일 때는 카운트를 temp에 추가하지 않는다. 
							temp += list.get(h - 1); // 압축한 문자열의 결과를 저장할 temp 변수에 문자열 추가
						} else {
							temp += Integer.toString(count) + list.get(h - 1); // 압축한 문자열의 결과를 저장할 temp 변수에 카운트 + 문자열 추가
						}
						count = 1; // 카운트 초기화
					}
					if (h == list.size() - 1) { // 맨 마지막 토막에 대해 처리
						if (count == 1) {
							temp += list.get(h);
						} else {
							temp += Integer.toString(count) + list.get(h);
						}
						count = 1;
					}
				}

				if (min > temp.length()) { // 최솟값 결정
					min = temp.length();
				}
				temp = ""; // temp 초기화
				list.removeAll(list); // 리스트 초기화
				j++; // 토막의크기 j를 증가시켜 1부터 문자열 s의 크기의 절반까지 나눔.
				i = 0; // substring() 메소드의 매개변수인 i를 0으로 초기화 하여 맨 앞글자부터 다시 토막내도록 초기화
				if (j > s.length() / 2) { // s.length() / 2 까지만 반복문을 돌리면 된다.
					break;
				}
			}

		}

		return min;
	}

	public static void main(String[] args) {

		StringCompression a = new StringCompression();

		System.out.println(a.solution("a"));
		System.out.println(a.solution("aabbaccc"));
		System.out.println(a.solution("ababcdcdababcdcd"));
		System.out.println(a.solution("abcabcdede"));
		System.out.println(a.solution("abcabcabcabcdededededede"));
		System.out.println(a.solution("xababcdcdababcdcd"));

	}

}

• 반복문의 조건으로 s.length() 까지 할 필요 없이 s.length()/2 까지만 확인해도 된다. 왜냐하면 예를 들어 'abcdabcdee' 라는 10자리의 문자열이 있을 때, 5개 이상, 즉 6개로 잘랐을 때 'abcdab', 'cdee' 로 잘라진다면, 잘려진 첫번째 문자열의 크기가 원본 문자열의 절반 크기보다 클 때 어차피 뒷 부분에 반복이 되지 않는다.
  Test Case 5 : 문자열 s 가 'a' 와 같이 한 글자일 때 처리를 해주어야 한다.
  length() : String의 길이, length : 배열의 길이, size() : Collections의 크기