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

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

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

약 26%의 정답률인 문제입니다.

문자열의 길이를 N이라 했을 때, 1개 단위 ~ N/2 단위까지 전부 검사하여 최소 값을 반환하면 됩니다.

예를 들어 7의 문자열을 가지면 1, 2, 3개 단위만 검사합니다.

단위의 수가 절반을 넘어가면 압축이 전혀 되지 않기 때문입니다.

 

 

예제 3번을 이 풀이 알고리즘을 적용하여 풀 때 3개의 단위에 대한 과정입니다.

 

---

메서드

int solution

i는 단위의 수를 증가시키며 검사합니다.

temp는 단위에 맞게 문자열을 잘라서 가지고 있다가 다음 문자열과 비교합니다.

만약 같은 문자열이라면 count를 증가시키고 다르다면 count와 문자열을 내놓습니다.

2개의 단위일 때 => "aaaa"는 2aa가 나오고, "aaab"는 aaab가 나옵니다.

 

j의 마지막 사이클에서 문자열을 신경 써서 잘라줍니다. 

7개의 문자열일 때 2개씩 자르면 마지막에서 에러가 나옵니다.

 

한 개의 단위 검사가 끝나면 최솟값을 최신화합니다.

 

class Solution {
	public static int solution(String s) {
		int min = s.length();
		
		for(int i = 1; i <= s.length()/2; i++) {
			StringBuilder sb = new StringBuilder();
			String temp = "";
			int count = 1;
			
			for(int j = 0; j < Math.ceil((double)s.length()/i); j++) {
				String now = s.substring(j*i, i*(j+1) >= s.length() ? s.length() : i*(j+1));
				if(!temp.equals(now)) {
					if(count != 1) {
						sb.append(count);
						count = 1;
					}
					sb.append(temp);
					temp = now;
				}
				else
					count++;
			}
			if(count != 1)
				sb.append(count);
			sb.append(temp);
			
			min = Math.min(min, sb.toString().length());
		}
		
		return min;
	}
}