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

문제

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

주어진 문자열에서 n개 단위로 문자열을 잘라 압축해 표현한 문자열 중 가장 짧은 것의 길이를 찾는 문제.
단, 문자가 반복되지않아 한번만 나타나는 경우 1은 생략한다

• 예시

s(문자열)	result
aabbaccc	7
ababcdcdababcdcd	9
abcabcdede	8
abcabcabcabcdededededede	14
xababcdcdababcdcd	17

• 문자열 “abcabcabcabcdededededede”의 경우
  1개 단위로 잘랐을 때 : abcabcabcabcdededededede (24자리, 압축되지않음)
  2개 단위로 잘랐을 때 : abcabcabcabc6de (15자리)
  3개 단위로 잘랐을 때 : 4abcdededededede (16자리)
  4개 단위로 잘랐을 때 : abcabcabcabc3dede (17자리)
  6개 단위로 잘랐을 때 : 2abcabc2dedede (14자리)

6개 단위로 잘라 압축한 14자리가 가장 짧다.

풀이

1. 입력받은 문자열 s의 길이를 answer(최소길이를 비교할 변수)에 저장한다.

2. s의 길이가 n이라면 1부터 n/2이하까지 반복하며 해당 숫자 단위로 문자를 압축하여 길이를 비교한다.
   즉, 6자리라면 1,2,3 길이 단위로 잘라 압축한다.

3. 문자열을 i길이 단위로 잘랐을 때 ㄱㄴㄷㄹ라고 하자.
   i길이로 잘랐을 때 총 길이는 len에다가 기록한다.
   첫번째 블록 ㄱ을 key에 저장하고, 현재 반복횟수는 1이다.

반복문 내부 뜯어보기
3-1. ㄴ을 key(ㄱ)와 비교한다.
같은 경우 : 반복횟수에 1을 추가한다. (반복횟수 : 2)
다른 경우 : key의 글자수와 반복횟수의 글자수를 len에 더해준다. ㄴ을 key에 저장한다. 반복 횟수를 1로 바꿔준다.
3-2. ㄷ를 key와 비교한다.
같은 경우 : 반복횟수에 1을 추가한다. (반복횟수 : 3)
다른 경우 : key의 글자수와 반복횟수의 글자수를 len에 더해준다. ㄷ을 key에 저장한다. 반복 횟수를 1로 바꿔준다.
…

1. len을 answer와 비교해서 최소값을 저장한다.

• 반복 횟수의 글자수를 얻는 법
  cnt : 반복횟수가 100 이라면 글자수는 3
  10이라면 글자수는 2

이때 Math의 log10을 이용하면 쉽게 구할 수 있다.
왜 1을 더하는지는 100을 가지고 생각하면 알수있다.

Math.log10(cnt) + 1 

소스코드

class Solution {
  static int answer;
	static String S;

	public int solution(String s) {
		S = s;
		answer = s.length();
		for (int i = 1; i < s.length() / 2 + 1; i++) {
			// i 길이 기준으로 자름
			zip(i);
		}
		return answer;
	}

	private void zip(int size) {
		int len = 0; // size만큼 잘랐을 때 문자열길이

		String key = S.substring(0, size);
		int start = size;
		int end = size * 2;
		int cnt = 1;

		while (end <= S.length()) {
			if(len>answer)
				return;
			if (S.substring(start, end).equals(key)) {
				cnt++;
			} else {
				if (cnt != 1)
					len += Math.log10(cnt) + 1 + key.length();
				else
					len += key.length();
				key = S.substring(start, end);
				cnt = 1;
			}
			start = end;
			end = end + size;
		}
		if (cnt != 1) {
			len += Math.log10(cnt) + 1 + key.length() + S.substring(start, S.length()).length();
		} else {
			len += S.substring(start, S.length()).length() + key.length();
		}
//		System.out.println(size + "단위 자르기 : " + len);
		answer = Math.min(answer, len);
	}
}

다른사람의 코드

class Solution {
    public int solution(String s) {
        int answer = 0;

        for(int i=1; i<=(s.length()/2)+1; i++){
            int result = getSplitedLength(s, i, 1).length();
            answer = i==1 ? result : (answer>result?result:answer);
        }

        return answer;
    }

    public String getSplitedLength(String s, int n, int repeat){
        if(s.length() < n) return s;
        String result = "";
        String preString = s.substring(0, n);
        String postString = s.substring(n, s.length());

        // 불일치 -> 현재까지 [반복횟수 + 반복문자] 조합
        if(!postString.startsWith(preString)){
            if(repeat ==1) return result += preString + getSplitedLength(postString, n, 1);
            return result += Integer.toString(repeat) + preString + getSplitedLength(postString, n, 1);
        }

        return result += getSplitedLength(postString, n, repeat+1);
    }
}