1.문자열 압축

<문제>

https://programmers.co.kr/learn/courses/30/lessons/60057?language=python3

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

<풀이>

• 이문제의 핵심은 "같은문자열이 반복되는것을 찾는다"이다. 상대적으로 긴 문자열이 반복될수록 압축되는 문자열의 길이도 짧아진다 생각했다. 
• 문제설명에도 나와있듯이 "abcabcdede"경우 2개단위로 자르면 abcabc2de가 되지만 3개 단위로 자를 경우 2abcdede로 압축이 가능해 길이가 더 짧아진다.
• step : 문자열을 자르는 단위
• prev : 압축의 기준이 되는 문자열, step길이 만큼 문자열을 비교할때 prev와 같은지 판단 만약 다르다면 prev 갱신

<파이썬 코드>

def solution(s):
    answer = len(s)
    for step in range(1,answer/2+1):
    	compressed = " "
        prev = s[0:step]
        for j in range(step,len(s),step):
        	if prev == s[j:j+stpe]:
            		count+=1
        	else:               
            		compressed +=str(count)+prev if count>=2 else prev
              		prev = s[j:j+step]
                	count = 1
        compressed +=str(count)+prev if count>=2 else prev
        answer = min(answer,len(compressed))
    return answer

<java코드>

import java.util.*;
class Solution {
    public int solution(String s) {
        int answer = 0;
        answer = s.length();
        if(s.length()==1) return 1;
        for(int i=1;i<=s.length()/2;i++){
            String compressed="";
            String prev = "";
            int count = 1;
            for(int j = 0;j<s.length()/i;j++){
                if(prev.equals(s.substring(j*i,(j*i)+i))){
                    count++;
                    continue;
                }
                
                if(count>1) {
                      compressed+=count+prev;
                      count=1;
                    }
                else{
                        compressed+=prev;
                        
                    }
                prev = s.substring(j*i,(j*i)+i);
                    
                    
                
            }
            if(count>1) {
                  compressed+=count+prev;
                  count=1;
                
                }
            else{
                  compressed+=prev;
                        
                }
            if(s.length()%i !=0){
                compressed+=s.substring(s.length()-s.length()%i,s.length());
            }
            answer = answer > compressed.length() ? compressed.length() : answer;
            
        }
            
            
        return answer;
    }
    public static void main(String[] args){
        solution sol = new solution();
        System.out.print(sol("abcabcdede"));
    }
}