[Java] 2020 KAKAO BLIND RECRUITMENT > 문자열 압축: 풀이 & 코드

문제: https://programmers.co.kr/learn/courses/30/lessons/60057?language=java 

 

 

문제 풀이:

• 변수
  • len: S의 길이
  • subLen: 압축 단위(길이)
  • count: 현재 문자열이 중복된 개수 (앞의 substring과 얼마나 중복되었는가)
• subLen은 최대 len/2이다.
  • 1부터 len/2까지 1씩 늘려가며 최적의 압축 단위를 찾는다.
• 1. 현재 위치에서 직전 subString(pre)과 현재 subString(cur)을 비교한다.
  • 즉, 현재 위치를 idx라고 할 때 다음과 같다.

String pre = s.substring(idx - subLen * 2 + 1, idx - subLen + 1); // 직전 sub string
String cur = s.substring(idx - subLen + 1, idx + 1); // 현재 sub string

• (pre.equals(cur))인 경우 
  • count[cur 위치] = count[pre 위치] + 1;
• (!pre.equals(cur))인 경우
  • 앞서 중복되었던 문자열들을 처리해 준다.
  • result += String(직전 문자열의 중복 횟수).length + subLen
    • abcabcabc -> 3abc
    • 주의: 이것처럼 중복 횟수가 일의 자리라면 (subLen+1)로 표현할 수 있지만, 십의 자리일 경우 (subLen+2)가 되므로 다음과 같이 처리해 줘야 한다.
• 2. 마지막으로 비교한 문자열은 count 값만 갱신하고 result에 값이 더해지지 않았다.
  • 중복 여부에 따라 result 값을 갱신해 준다.
• 3. subLen으로 나누어떨어지지 않는 경우 길이 (len % subLen)를 가지는 마지막 문자열은 무조건 그대로 더해진다.

 

 

소스 코드:

import static java.lang.Math.min;

class Solution {
    public int solution(String s) {
        int answer = 1000;
        for (int i = 1; i <= s.length() / 2; i++) {
            answer = min(answer, compress(s, i));
        }

        return answer;
    }

    public int compress(String s, int subLen) {
        int len = s.length();
        int result = 0;
        int[] count = new int[s.length()];

        int idx = subLen * 2 - 1;
        while (idx < len) {
            String pre = s.substring(idx - subLen * 2 + 1, idx - subLen + 1);
            String cur = s.substring(idx - subLen + 1, idx + 1);
            if (pre.equals(cur)) count[idx] = count[idx - subLen] + 1;
            else {
                if (count[idx - subLen] == 0) result += subLen;
                else result += String.valueOf(count[idx - subLen] + 1).length() + subLen;
            }
            idx += subLen;
        }
        
        // 마지막 subString에 대한 처리
        if (count[idx - subLen] == 0) result += subLen;
        else result += String.valueOf(count[idx - subLen] + 1).length() + subLen;

        result += (len % subLen); // subLen으로 나누어떨어지지 않아서 압축할 수 없는 문자열
        return result;
    }
}