프로그래머스 - [Level 1] 문자열 압축(JAVASCRIPT)

프로그래머스 문자열 압축 [KAKAO]

카테고리 : 문자열

[참고]
자바스크립트
1) substring(시작위치,종료위치)
	
	- 시작위치부터 종료위치 전까지의 문자열을 추출한다.
	- 문자열의 길이를 초과해도 자동 보정(?)이 된다.
        
	var str="123456";
	console.log(str.substring(5,6)); => 6
	console.log(str.substring(1,3)); => 23
	console.log(str.substring(1,2)); => 2
	console.log(str.substring(5,100)); => 6

2) substr(시작위치,길이)

	var str="123456";
	console.log(str.substr(5,1)); => 6


[문제 풀이 과정]

1) 문자열은 최대 문자열 길이/2 만큼 잘라야 압축이 가능하다.

=> [1 ~ 문자열 길이/2]범위 만큼 for문을 돌며 문자열을 압축하자.

   for(var len=1;len<=s.length/2;len++)

2) "xababcdcdababcdcd"
"문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다."

=> index = 0 부터 기준 길이(len)만큼 자르면서, 비교해나가자

   for(idx=len;idx<=s.length;idx+=len){
       if(뒷 문자열과 같다면){
           카운트를 증가시켜준다.
       }
       else{ // 그렇지 않다면
           
           새롭게 만들어지는 문자열에 자른 문자열을 더 해준다.
           단, 카운트가 2이상일 경우에는 카운트를 자른 문자열 앞에 붙여준다.
           비교 문자열을 [현위치 + 기준 길이]의 문자열로 갱신해준다.
           
       }
   }

=> 잘린 문자열의 마지막 값을 따로 더 해줘야한다.
위 조건문은 문자열이 현 문자열 !== 뒷 문자열 일때,
새로운 문자열에 자른 문자열을 더 해준다.
 그렇기 때문에 현 문자열이 가장 마지막 문자열일 경우에는, 
비교대상이 없어 문자열이 더해지지 않는다. 이점에 유의하자.

ex) "abcd", len=2 일 때,
    "cd"의 다음 문자열 ? 없음. 비교할 수 없다.

[오류]

for(idx=len;idx<s.length-len;idx+=len)

처음 for 문의 범위를 위와 같이 잡았다.
예를들어 "aabbaccc" 길이가 8인 문자열 s가 있다고하자.
압축단위가 3일 때, 
    
    for(idx=3;idx<5;idx+=3)

idx가 3일 때, tmp="aab", 뒷 문자열="bac"가 다르다.
따라서, str=aab, tmp=bac가 된다.
이때, idx=6이 되어 for문을 탈출하게 된다.

결국, 만들어지는 문자열 str=aab+tmp인 "aabbac"가 된다.
마지막으로 잘리는 문자열이 더 해지지 않는 문제가 생기는 것이다.

"인덱스를 조절하는 문제를 효율적으로 풀이하는 방법을 고민해보자."

소스코드

function solution(s) {
    var answer = s.length;

    for(var len=1;len<=s.length/2;len++){
        var str="";
        var idx=0;
        var tmp=s.substring(0,len);
        var cnt=1;
        for(idx=len;idx<=s.length;idx+=len){
            if(tmp===s.substring(idx,idx+len)){
                cnt++;
            }
            else{
                if(cnt===1) str+=tmp;
                else str+=cnt+tmp;
                cnt=1;
                tmp=s.substring(idx,idx+len);
            }
        }
        
        if(cnt===1) str+=tmp;
        else str+=cnt+tmp;
        
        answer=Math.min(answer,str.length);
    }
    return answer;
}

다른 사람의 코드

1) 스트링 리터럴 사용

str+=count+tmp = > str+=`${count}${tmp}`;

2) 함수형 프로그래밍은 아직도 어렵다..

const solution = s => {
  const range = [...Array(s.length)].map((_, i) => i + 1);
  return Math.min(...range.map(i => compress(s, i).length));
};

const compress = (s, n) => {
  const make = ([a, l, c]) => `${a}${c > 1 ? c : ''}${l}`;
  return make(
    chunk(s, n).reduce(
      ([a, l, c], e) => e === l ? [a, l, c + 1] : [make([a, l, c]), e, 1],
      ['', '', 0]
    )
  );
};

const chunk = (s, n) =>
  s.length <= n ? [s] : [s.slice(0, n), ...chunk(s.slice(n), n)];