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

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

프로그래머스

---

작년 하반기 카카오 코딩테스트 문제입니다. 온라인으로 봤던 기억이 있는데 그때는 풀어보려고 해도 안풀렸었는데 거의 반년?이 지나고 다시 침착하게 풀어보니까 풀 수 있었습니다. 처음에 코드를 제출했는데 5번 테스트케이스만 오답이 나왔습니다. 질문하기를 눌러보니 문자열 길이가 "a" 같은 1짜리가 들어오게 되면 처음에 설정해 두었던 MAX_VALUE 값이 나와서 틀리는 거였습니다.

[ 문제 풀이 ]

1. len 이라는 변수는 문자열의 길이를 몇으로 압축할것인지 나타내는 변수입니다. 문자열의 길이 / 2 만큼 까지 수행하는 이유는 문자열의 길이 반이 넘어가게 되면 나눈 문자열이 같은지 확인할 수 없기 때문입니다. StringBuilder sb 에는 해당 len 길이로 압축한 문자열을 저장합니다.

2. 이제 문자열의 처음부터 길이만큼 잘라서 같은 문자열이 몇개 있는지 확인합니다. n은 같은 문자열이 몇개 있는지 갯수를 나타내는 변수입니다. i+len 이 문자열의 길이를 벗어나면 남은 문자열을 StringBuilder에 append 해주고 반복문을 빠져나갑니다.

3. String st 에는 문자열에서 len 만큼 비교할 문자열을 substring으로 저장합니다. idx에는 잘라낸 문자 다음 인덱스를 저장해서 len 만큼 더하면서 잘라진 문자열과 비교하여 같으면 갯수를 카운팅해서 저장합니다. 같지 않으면 반복문을 빠져나옵니다.

4. n 에 저장된 숫자가 1이 아니라면 문자열을 압축할 수 있다는 뜻이므로 sb에 n을 먼저 추가하고 반복을 수행하는 인덱스 i에 잘린 길이 len이 몇개 있는지 곱해서 건너뛰어 줍니다.

5. n 에 저장된 숫자가 1이라면 문자열을 압축할 수 없다는 뜻이므로 i 에 len 만큼 더해줘서 반복문을 넘어갑니다.

6. len 길이로 문자열이 압축되면 최솟값을 answer에 저장하고 마지막에 출력합니다.

---

class Solution {
    public int solution(String s) {
        if(s.length() == 1) return 1;
        int answer = Integer.MAX_VALUE;
        StringBuilder sb = null;
        
        for(int len=1; len<=s.length()/2; len++) {
        	sb = new StringBuilder();
        	
        	for(int i=0; i<s.length(); i++) {
        		int n = 1;
        		
        		if(i+len >= s.length()) {
        			sb.append(s.subSequence(i, s.length()));
        			break;
        		}
        		
        		String st = s.substring(i, i+len);
        		
        		int idx = i+len;
        		
        		while(idx+len <= s.length()) {
        			if(s.substring(idx, idx+len).equals(st)) {
	        			n++;
	        			idx += len;
        			} else break;
        		}
        		
        		if(n != 1) {
        			sb.append(n);
        			i += (len*n)-1;
        		} else {
        			i += len-1;
        		}
        		sb.append(st);
        	}
        	answer = Math.min(sb.length(), answer);
        }
        return answer;
    }
}