[Programmars] 문자열 압축

문제

• Programmars 60057
• 문제의 저작권은 Programmars에 있습니다.

접근방식

1. 문자열을 최대로 나눌 수 있는 크기는 길이/2이다. 나눌 수 있는 크기만큼 돌면서 경우의 수를 구해준다.

for (int size = s.length() / 2; size >= 1; size--)
			answer = Math.min(answer, slice(s, 0, size, 1));

1. slice(String s, int i, int size, int cnt)
   • 문자열을 돌면서 크기 size 만큼 나누기 위해 substring(현재 인덱스, 마지막 인덱스)를 이용해 list에 저장, substring()을 이용하면 나누어 떨어지지 않는 경우 남는 문자열이 있기 때문에 이는 조건 처리 ex)abcbabcb를 size=3만큼 나누면 cb가 남음
   • list를 돌면서 나눈 문자열을 하나씩 꺼내면서 현재 문자열 now와 다음 문자열 next를 비교
     • 같으면 cnt증가, 인덱스 증가시켜서 다음 문자열 비교
     • 다르면 종료 ⇒ 현재까지 계산한 cnt를 sb 에 append, cnt==1인 경우는 필요없으니까 조건처리
   • 이렇게 압축한 결과가 sb에 담기면 그 길이를 return
2. 1로 돌아와 return받은 길이와 answer를 비교해서 더 짧은 경우에만 answer바꿔줌

import java.io.*;
import java.util.*;

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

		// 1. 최대 나눌 수 있는 크기인 N/2(가장 짧은 길이)부터 자르기
		for (int size = s.length() / 2; size >= 1; size--)
			answer = Math.min(answer, slice(s, 0, size, 1));

		return answer;
	}

	private static int slice(String s, int i, int size, int cnt) {
		List<String> list = new ArrayList<>();
		StringBuilder sb = new StringBuilder();

		// 2. size만큼 s를 앞에서부터 잘라서 list에 넣음
		while (true) {
			if (i + size > s.length()) { //나누어 떨어지지 않는 경우 처리
				list.add(s.substring(i, s.length()));
				break;
			}
			list.add(s.substring(i, i += size));
		}

		// 3. list를 돌면서 같은 문자열 있는지 체크
		i = 0;
		String now = list.get(i);
		String next = "";
		
		while(true) {
			//마지막 인덱스
			if(i >= list.size()-1) {
				if(cnt >= 2) sb.append(cnt+"");
				sb.append(now);
				break;
			}
			
		    next = list.get(i+1);
		    
		    if(now.equals(next)) {
		    	cnt++; i++;
		    }else {
		    	if(cnt >= 2) sb.append(cnt+"");
		    	sb.append(now);
		    	now = next;
		    	cnt = 0;
		    }
		}
		return sb.length();
	}
}