문제

programmers 문자열 압축 문제 보러가기



풀이 방법

가장 짧게 압축할 수 있는 N/2 부터 1까지 줄여가며 최초 문자(string)을 정한 다음 2중 for문을 돌려 일치할때마다 count를 증가시켜 StringBuilder에 append해주었다. 카카오 인턴 시험을 준비하면서 다시 풀은 문제였는데 이전에 풀이를 보니 한숨만 나왔다 …



풀이

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

		int n = s.length();
        
        if(n == 1) return 1;

		StringBuilder sb;
		for (int i = n / 2; i > 0; i--) {
			sb = new StringBuilder();
			String now = s.substring(0, i);
			int count = 1;
			for (int j = i; j < n; j += i) {
				if(j + i > n) {
					sb.append(count > 1 ? count : ""); // 이전 count sb에 저장 후
					sb.append(now);
					sb.append(s.substring(j, s.length())); // 뒤에 나머지 알파벳 붙이고
					break;
				}
				
				String next = s.substring(j, j + i);
				
				if(now.equals(next)) count++;
				else {
					sb.append(count > 1 ? count : "");
					sb.append(now);
					count = 1;
					now = next;
				}
				
				if(j + i == n) {
					sb.append(count > 1 ? count : "");
					sb.append(next);
					break;
				}
			}

			answer = Math.min(sb.toString().length(), answer);
		}

		return answer;
	}
}