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

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

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

import java.util.*;
class Solution {
    public int solution(String s) {
        int result = Integer.MAX_VALUE;
        for(int i=1; i<=(s.length()/2)+1; i++){
            result = Math.min(encoding(i, s), result);
        }
        return result;
    }

    int encoding(int n, String s){
        StringBuilder sb = new StringBuilder();
        for(int i=0; i< s.length(); i+=n){
            if(i+n > s.length()){
                sb.append(s.substring(i));
                break;
            }

            String temp = s.substring(i, i+n);
            int cnt = 1;
            for(int j=i+n; j+n<= s.length(); j+=n){
                if(temp.equals(s.substring(j,j+n))){
                    cnt++;
                    i=j;
                    continue;
                }
                break;
            }

            if(cnt > 1){
                sb.append(cnt).append(temp);
            }
            else{
                sb.append(temp);
            }
        }
        return sb.length();
    }
}

encoding(int n, String s)

n은 몇 개 단위로 압축할지를 나타냅니다.

 

aabbaccc의 경우

2a2ba3c

aa bb ac cc

aab bac cc

aabb accc

위와 같이

문자열의 길이(8) / 2의 단위 만큼 압축할 수 있습니다.

따라서 encoding 반복횟수를 위와 같이 정해주었습니다.

+1을 한 이유는 문자열 길이가 1개일때의 예외처리를 한 것인데 +1을 하지않고 따로 조건을 빼서 리턴하는게 효율적으로 보입니다.

 

encoding에서는

1. 첫번째 문자단위부터 시작하여 다음 문자단위와 비교합니다.

2. 같으면 i의 위치를 j로 옮겨주고 그 다음 문자단위와 비교합니다.

3. 비교하는 문자열이 다른 경우 루프문을 빠져나옵니다.

4. 같은 문자열의 갯수에 따라 StringBuilder에 append 합니다.