프로그래머스 - 문자열 압축(Java)

구현 문제입니다.

특정 알고리즘이 필요하지 않는 문제입니다,

단, 시간을 줄이기 위해서는 한 가지 아이디어가 필요합니다.

"한 번에 압축될 수 있는 최대 문자의 크기는 전체의 절반이다." 입니다.

 

'aabbcc'가 있다고 가정하겠습니다.

이 문자를 압축하면 '2a2b2c'입니다.

문자열의 길이는 6이고, 한 번에 최대로 압축될 수 있는 문자의 크기는 2입니다.

 

'aaabbb'가 있다고 가정하겠습니다.

이 문자를 압축하면 '3a3b'입니다.

문자열의 길이는 6이고, 한 번에 최대로 압축될 수 있는 문자의 크기는 3입니다.

 

'ababcdcdababcdcd'가 있다고 가정하겠습니다.

이 문자를 압축하면 '2ababcdcd'입니다.

문자열의 길이는 16이고, 한 번에 최대로 압축될 수 있는 문자의 크기는 8입니다.

 

'ababcdcdxababcdcd'가 있다고 가정하겠습니다.(중간에 x가 있습니다.)

이 문자를 압축하면 '2ab2cdx2ab2cd'입니다.

문자열의 길이는 16이고, 한 번에 최대로 압축될 수 있는 문자의 크기는 2입니다.

 

눈치 채셨나요? 최대 절반을 기준으로 앞, 뒤로만 앞축이 될 수 있습니다.

'aaaabb'는 어떨까요?

이 문자를 압축하면 '4a2b'입니다.

어? 그러면 한 번에 최대로 압축될 수 있는 크기는 4아닌가요? 라고 할 수 있습니다만, 아닙니다.

'aaaabb'는 'a'를 기준으로 한 번에 최대 한 번 압축하는 것을 네 번, 'b'를 기준으로 한 번에 최대 한 번 압축한 것을 두 번 반복한 결과입니다.

 

위에서 제가 '한 번에 최대로 압축'을 강조한 이유가 여기에 있습니다.

 

아직도 긴가민가하시다면 첨부된 코드를 보면서 디버깅 또는 출력을 찍어보시면 이해가 가실 것 입니다.

 

[구현 코드]

class Solution {
    public int solution(String s) {
        int answer = 0;
            //반환되는 문자열 길이
            int max = s.length();

            //최대 문자열의 절반만큼을 기준으로 삼아 문자열 압축
            for (int i = 1; i <= (s.length() / 2); i++) {
                int left = 0; //기준점 시작 위치
                int right = left + i; //비교 시작 위치
                int count = 1; //문자열 중복 횟수
                String s1 = s.substring(left, left + i); //중복을 찾는 문자열의 길이
                StringBuilder sb = new StringBuilder(""); //문자열 압축 후 저장되는 문자열

                while (right + i <= s.length()) { //비교하는 문자의 위치가 전체 길이를 넘지 말아야 함
                    String s2 = s.substring(right, right + i); //중복을 찾는 비교 문자열
                    if (s1.equals(s2)) { //중복일 때(압축 가능할 때)
                        count++;
                    } else { //중복이 아닐때
                        if (count > 1) sb.append(count); //직전에 중복된 문자가 있을 때
                        sb.append(s1);
                        s1 = s2; //비교 문자를 바꿈
                        count = 1; //문자가 변경 되었으니 중복 획수도 변경
                    }
                    right = right + i; //다음 비교 위치 이동
                }
                //반복문이 종료되고 마지막으로 남는 문자열 추가
                if (count > 1) sb.append(count);
                String tmp = s.substring(right - i, s.length());
                sb.append(tmp);

                //최저 길이를 저장
                if (sb.length() <= max) max = sb.length();
            }
            answer = max;

            return answer;
    }
}