[2020 KAKAO BLIND RECRUITMENT] 문자열 압축

2020 KAKAO BLIND RECRUITMENT 문자열 압축

유형

• 문자열

"aaaaaaaaaaa"와 같이 다양한 테스트케이스를 고려하는 것이 중요한 문제였다.

코드

import java.util.ArrayList;
import java.util.List;

class Solution {
    public int solution(String s) {
        int min = s.length();
        
        for(int i = 1; i <= s.length(); i++) {
            int compressedLength = compress(s, i);
            if(compressedLength < min) {
                min = compressedLength;
            }
        }
        
        return min;
    }
    
    static class RepeatedStr {
        String str;
        int repeatedNum;

        public RepeatedStr(String str, int repeatedNum) {
            this.str = str;
            this.repeatedNum = repeatedNum;
        }
    }

    private int compress(String s, int unit) {
        List<RepeatedStr> list = new ArrayList<>();
        int share = s.length() / unit;
        int remainder = s.length() % unit;

        for(int i = 0 ; i < share; i++) {
            String substring = s.substring(i * unit, (i + 1) * unit);
            if(i != 0 && list.get(list.size() - 1).str.equals(substring)) {
                list.get(list.size() - 1).repeatedNum++;
            } else {
                list.add(new RepeatedStr(substring, 1));
            }
        }

        int length = 0;
        for (RepeatedStr str: list) {
            length += unit;
            if(str.repeatedNum != 1) {
                length += String.valueOf(str.repeatedNum).length();
            }
        }

        length += remainder;

        return length;
    }
}