문자열 압축

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

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

2020카카오 블라인드 공채에서 풀었던 문제이다. 중복되는 문자열을 줄이는게 핵심이다. 중복되는 문자열의 길이는 같아야한다. (가장 최적으로 중복을 없개는 게 아니다. Ex> aaabcbc != 3a2bc)

 

그래서 반복은 최대 문자열 길이의 반까지 될 수 있다. 길이가 10인 문자열에서 6인 문자열이 중복 될 수는 없기 때문이다. 그래서 길이가 1부터 문자열의 반까지 앞에서부터 잘라서 비교를 해보았다.

 

그래서 기준 문자열과 다음 문자열이 같으면 ++, 다르면 줄인 문자열을 생성해주었다. 그리고 더 이상 반복이 안되는 경우 (나머지)는 그냥 줄인 문자열 뒤에 붙여주었다.

 

여기서 길이가 1인 문자열인 케이스를 놓쳐서 조금 헤맸었다.

 

다음은 코드 전문이다.

 

class Solution {
    public int solution(String s) {
        int answer = 10000;
        int length = s.length();
        String before = new String();
        String after = new String();
        String temp = new String();
        int top = 0;
        int count = 1;
        
        for(int i = 1; i <= length/2+1; i++) {
        	before = s.substring(0,i);
        	top += i;
        	while(true) {
        		// 다음을 볼 수 있다면
        		if(top+i <= length) {
	        		after = s.substring(top,top+i);
	        		// 같으면 ++
	        		if(before.equals(after)) {
	        			count++;
	        		}
	        		// 다르면 바꾸기
	        		else {
	        			if(count > 1) {
	        				temp = temp + count + before;
	        			}
	        			else {
	        				temp += before;
	        			}
	        			before = after;
	        			count = 1;
	        		}
	        		top += i;
        		}
        		else {
        			if(count > 1) {
        				temp = temp + count + before + s.substring(top);
        			}
        			else {
        				temp += s.substring(top-i);
        			}
        			break;
        		}
        	}
        	if(answer > temp.length()) {
        		answer = temp.length();
        	}
        	count = 1;
        	top = 0;
        	temp = "";
        }
        
        return answer;
    }
}