[2020 KAKAO BLIND RECRUITMENT]文字列圧縮

10864 ワード

2020 KAKAO BLIND RECRUITMENT文字列圧縮

を選択します。

  • 文字列
  • 「aaaaaaa」のような多くのテストケースを考慮することは重要な問題である.

    コード#コード#

    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;
        }
    }