[프로그래머스] 문자열 압축 (Java)

문제

프로그래머스

 

알고리즘

없음

 

풀이

압축 단위를 1씩 늘리면서 압축하고 최소 길이를 갱신한다.

이때, 압축 단위가 절반이 넘어가면 압축을 하지 않은 것과 동일하므로 압축 단위를 절반까지만 증가시킨다.

 

압축

압축 단위만큼 substring 한 문자열을 token을 대상으로 다음 연산을 진행한다.

 

1. token이 이전과 동일하다면 count 증가

2. token 이전과 동일하지 않다면

    (1) count가 1 이상이라면 count 삽입 

    (2) token 삽입 및 count = 1, before = token 저장

 

만약 압축 단위만큼 늘린 값이 문자열의 길이보다 커지면 압축이 불가능하므로 남은 문자열을 그냥 이어붙인다.

 

코드

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

		for (int i = 1; i <= s.length() / 2; i++) {
			StringBuilder res = new StringBuilder();
			String before = "";
			int count = 1;
			int j = 0;

			for (; j <= s.length(); j += i) {
				if (j + i > s.length()) {
					if (count > 1)
						res.append(count);
					res.append(before);
					res.append(s.substring(j));
					break;
				}

				String token = s.substring(j, j + i);

				if (token.equals(before)) {
					count++;
				} 
				else {
					if (count > 1)
						res.append(count);
					res.append(before);
					count = 1;
					before = token;
				}
			}
			min = Math.min(min, res.length());
		}

		return min;
	}
}