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

문제 출처 - Programmers

문제는 여기

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

---

[풀이]

1. 문자열의 절반까지 반복문을 돌린다.

2. substring을 사용해 압축시킬 문자열을 구해준다.

3. 압축시킨 문자열을 사용해 이후에 문자열과 비교를 한다.

4. 3. 에서 비교를 하여 같다면 횟수를 증가시킨다.

5. 3. 에서 비교를 하여 다르다면 아래 내용을 실행한다.

6. 패턴의 사용 횟수가 1이라면 압축을 못 시킨 것이므로 넘어가고 아니라면 사용 횟수를 입력해준다.

7. 현재 패턴을 입력해준다.

8. 새로운 패턴으로 갱신시켜주고 사용 횟수를 1로 초기화해준다.

9. 위 과정을 반복하고 마지막에 압축을 못시킨 것을 압축시켜준다.

10. 압축시켜 만들어진 문자열 + (전체 문자열 길이 % 압축 문자열의 길이)와 현재까지의 최솟값을 비교해 최솟값을 갱신해준다.

11. 결과를 출력해준다.

[접근]

1. 문제를 읽고, 압축시킬 길이를 늘려가면서 체크하여 압축시키면 되겠다고 생각을 하였다.

2. 원하는 문자열의 길이만큼 잘라내는것은 substring을 사용하면 편하게 할 수 있을 것 같았다.

[실수]

1. 문자열의 길이가 1일 때 따로 예외처리를 했어야 하는데 이 점을 간과하였다.

2. 문자열을 압축시킨 후, 압축된 문자열의 길이만 계산해서 체크했는데 문자열 압축을 시킬 길이가 되지 않는 경우에 남아있는 문자열들의 길이를 더해줘야 하는 것을 놓쳤었다.

[코드]

class Solution {
    public int solution(String s) {
        int answer = Integer.MAX_VALUE;
        int len = s.length();
        
        // 입력받는 문자열의 길이 == 1일 때 예외처리
        if (s.length() == 1)
            return 1;
        
        // 압축을 시키기 위해선 앞의 길이와 뒤의 길이가 적어도 동일해야하므로
        // len / 2까지만 반복
        for (int i = 1; i <= len / 2; i++) {
            // substring을 사용해서 압축시킬 문자열의 길이를 늘려나가기
            // pattern == 압축시킬 문자열 패턴
        	String pattern = s.substring(0, i);
        	int cnt = 1; // pattern을 몇 번 사용했는지
        	String str = "";
            
        	for(int j = i; j <= s.length() - i; j += i) {
                // 문자열과 다음에 오는 문자열이 일치하는지 체크
        		if (pattern.equals(s.substring(j, j + i))) {
    				cnt++; // pattern을 사용해서 압축시켰으니까 횟수 증가
    			} else {
                    // 압축을 했으면
    				if(cnt > 1) {
                        // 압축된 횟수를 적어주기 ex) abab > 2ab
    					str += cnt + "";
    				}
                    // 압축시킨 패턴을 붙이기
   				    str += pattern;
                    // 다른 문자열이 왔으니까 새로운 패턴을 압축시킬 패턴으로 갱신
    				pattern = s.substring(j, j + i);
                    // 처음 사용하는 것이니 1로 초기화
    				cnt = 1;
    			}
        	}
        	
            // 마지막에 압축시키지 않은 문자열 패턴을 압축시키기
        	if (cnt > 1) {
    			str += cnt + "";
    		}
    		str += pattern;
    		
            // i개 단위로 자르고 남은 문자열 길이
    		int remain = s.length() % i;
            // 최솟값 갱신
    		answer = Math.min(answer, str.length() + remain);
        }
        
        return answer;
    }
}