[프로그래머스] [자바] [카카오] 문자열 압축

https://programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

접근 방식

• Brute Force

 

이전에는 문제를 풀 때 절차적으로만 작성을 했었는데 최대한 객체지향적으로 풀어야 겠다고 생각하게 된 계기는 유튜브 개발바닥 에서 나온 사람들의 공통점으로 코드를 얼마나 객체지향적으로 풀었는 지를 본다고 했기에 이전에 풀었던 내용들을 최대한 객체지향적으로 풀려고 노력했다.

 

public class Solution {
    public int solution(String s) {
        Zip zip = new Zip(s);
        return zip.compress();
    }
    public static class Zip {
        private final String sentence;
        public Zip(String sentence) {
            this.sentence = sentence;
        }
        
        private boolean compareString(String sentence,int prev, int cur,int i) {
            return sentence.substring(prev,prev+i).equals(sentence.substring(cur,cur+i));
        }
        
        private int increase(int tmp, int count,int i){
            if (count==1){
                tmp += i;
            }else{
                tmp += String.valueOf(count).length() + i;
            }
            return tmp;
        }
        
        private int compressed(String sentence,int answer,int i, int size) {
            int prev = 0;
            int cur = prev + i;
            int count;
            int tmp = 0;
            while(cur<=size) {
                count = 1;
                while (cur+i<=size && compareString(sentence,prev,cur,i)){
                    cur+=i;
                    count++;
                }
                tmp = increase(tmp,count,i);
                prev = cur;
                cur+=i;
            }
            tmp += size - prev;
            answer = Math.min(answer, tmp);
            return answer;
        }

        public int compress() {
            int size = sentence.length();
            int answer = 1000;
            for(int i =1; i<=size/2+1 ; i++){
                answer = compressed(sentence,answer,i,size);
            }
            return answer;
        }
    }
}

 

 

Zip

compareString

기준 문자열은 prev에서 prev+i 만큼의 문자열이며 [cur,cur+i)에 해당하는 문자열을 비교해 참/거짓 값을 반환하도록 했다.

 

increase

갯수가 1일 때는 압축할 문자열이 없는 것이므로 단순히 i 만큼만 더하고 그렇지 않다면 갯수를 문자열로 변환한 것의 길이 + 간격을 더해준다.

 

compressed

i 만큼의 간격으로 계속 나아가면서 압축할만한 문자열이 있는지 확인하고 반환값으로 총 길이를 반환한다.

 

compress

여기서 핵심은 size/2+1이다. +1을 안하는 경우 길이가 1일 때 해당 루프를 돌지 않기 때문에 이 점을 유의해서 풀어야 한다.