[21/09/01 복습] 문자열 압축

문자열 압축

반례 : 문자열길이가 1일때 답은 1임 -> 기존의 코드는 첫번째 포문에 안들어가게됨

function solution(s){
  	// 반으로 나누게 되면 문자열 길이가 1일때 0이되어서 첫번째 포문이 들어가지 않게되고 result가 그대로 답으로 출력되어버림
    // const finish = Math.floor(s.length / 2);
    let result = 10000000000;
    for(let i=1;i <= s.length;i++){
        let string = ''
        let cache = s.slice(0,i);
        let count = 1;
        let j = i;
        let c;
        while( c !== ""){
            c = s.slice(j,j+i)
            if(cache === c){                
                count++;
            }else{
                string += `${count === 1 ? '' : count}${cache}`;                
                count = 1;                
            }            
            cache = c;            
            j = j + i;
        }
        result = Math.min(result,string.length);
        
    }
    return result;
}

function solution(s){
    let result = 10000000000;
    for(let i=0;i <= Math.floor(s.length / 2);i++){
      // 쪼개는 갯수
        const splitNumbers = i + 1;
        
      // splitNumbers개로 쪼갤 때 압축되는 문자열 변수
        let compressionString = ''
        
        // 이전의 쪼개진 문자열
        let cache = s.slice(0,splitNumbers);
        // 이전거랑 같은 경우
        let cacheHit = 1;
        // splitNumbers 개로 잘려진 문자열
        let splitString;
        // 순회하는 변수
        let j = splitNumbers;
        
      
        // 잘려지는 문자열이 없을 때 까지 한다.
        while( splitString !== ""){
            
            splitString = s.slice(j,j+splitNumbers)
            
            if(cache === splitString){          
                
                cacheHit++;
                
            }else{
                
                compressionString += `${cacheHit === 1 ? '' : cacheHit}${cache}`;        
                
                cacheHit = 1;                
                
            }            
            cache = splitString; 
            
            j = j + splitNumbers;
        }
        result = Math.min(result,compressionString.length);
        
    }
    return result;
}

밑은 함수로 분리한 것이다.

function compression(s,splitNumbers){
    let splitString;        
    let compressionString = ''
    let cache = s.slice(0,splitNumbers);        
    let cacheHit = 1;        
    let i = splitNumbers;
      while( splitString !== ""){
            
            splitString = s.slice(i,i+splitNumbers)
            
            if(cache === splitString){          
                
                cacheHit++;
                
            }else{
                
                compressionString += `${cacheHit === 1 ? '' : cacheHit}${cache}`;        
                
                cacheHit = 1;                
                
            }            
            cache = splitString; 
            
            i = i + splitNumbers;
    }
    return compressionString
}
function solution(s){
    let result = 10000000000;
    for(let i=0;i <= Math.floor(s.length / 2);i++){
        result = Math.min(result,compression(s,i+1).length);   
    }
    return result;
}

느낀점

반례찾을때는 애매한 경우, 극단적인 경우를 우선적으로 조사하자.