[프로그래머스-JS] level 2 문자열 압축 <공사중>

 

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

프로그래머스

 

나의 코드 

 

function solution(s) {
    let answer = [];
    for(k=1; k<=s.length/2; k++){
        const regex = new RegExp(`[a-z]{${k}}`,"g");
        const cut  = s.match(regex)
        const rest = s.slice(s.length - (s.length % k),s.length)
        let result = "";
        let pre = 1;
        for(i=0; i< (cut.length); i++){
        if(cut[i] == cut[i+1]){
           pre += 1;
        }else{
           result += ((pre === 1 ? "" : pre) + cut[i]);
           pre = 1
            }
        }
        if(rest) result += rest
        if(result.match(/\d/g)){
            answer.push(result.length)
        }
    }
    return answer[0] ? Math.min(...answer) : s.length ;
}

 

 

 

 

전체적인 생각은 

정규표현식으로 1개 단위로 자를때 2개단위로 자를때 등등  s.length/2 개 단위로 자르고 각각의 문자열 길이를 추출한뒤  최소값을 반환하는 코드이다.  

 

정규표현식에서 n개 단위로 자르면 

제일 안쪽에 있는 for문으로 중복되는 알파벳 갯수를 pre에 넣는다. 

중복성이 끊기면  result에   pre에 저장된 숫자와 현재 배열 값을 넣는다.  

그러면 2a이런식으로 result에 저장이된다. 

그리고 다시 다음 알파벳의 중복 갯수를 구한다. 

 

그런데 이렇게만 하면 몇몇의 경우에 오답을 출력한다. 

 

 

예를들어  세 번째 예제 

"abcabcdede" 총 문자길이가 10인데  정규표현식으로 3개단위로 자르면 

"abc" "abc "ded"  이렇게 되어서 2abcded가 된다. 

이렇게하면 틀린답이나온다. 

정답은 2abcdede가 되어서 길이가 8이 나와야한다. 

즉 10개의 문자길이를 3개 단위로 자르면 마지막 문자가 남는데  만약 이것이 답이라면 

나머지문자를 길이에 포함을 시키지 못해 오답이나오는 것이다

이것을 방지하기 위해 

const rest = s.slice(s.length - (s.length % k),s.length)

이 작업을 한 것이다. 

이렇게 하면 n개를 자르고 나머지가 남으면 그 나머지를 뒤에다 붙여주는 것이다. 

 

 

더 배워야할 개념

 

1. new RegExp()   즉 정규표현식에 변수 넣는 법

 

 

다른 사람 풀이 

풀이 1 )

원본에서 길이만 조금 수정해줬다.

 

재귀 함수를 많이 사용한 코드이다.

 

처리속도는 느리다.  

역시ㅣ 재귀 함수는 느리다. 

 

const solution = s => {
  const range = [...Array(Math.round(s.length/2))].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)];

변수를 조금 더 이해하기 쉽게 풀면

 

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

const compress = (s, cutNumber) => {
   const make = ([textArray, lastText, TextCount]) => `${textArray}${TextCount > 1 ? TextCount : ''}${lastText}`;
  return make(
    chunk(s, cutNumber).reduce(
      ([textArray, lastText, cutNumber], currentValue) => currentValue === lastText ? [textArray, lastText, cutNumber + 1] : [make([textArray, lastText, cutNumber]), currentValue, 1],
      ['', '', 0]
    )
  );
};
const chunk = (s, cutNumber) =>
  s.length <= cutNumber ? [s] : [s.slice(0, cutNumber), ...chunk(s.slice(cutNumber), cutNumber)];

 

 

이것도 이해하기 어려우면 예제를 통해서 이해해보자 

 

입력값(s) : "abcabcdede"

const solution = s => {
  const range = [...Array(Math.round(s.length/2))].map((_, i) => i + 1);
    console.log("range : ", range) // range :  [1, 2, 3, 4, 5]

range배열의 각각의 숫자는 n개 단위로 문자를 끊겠다는 숫자이다. 

 

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

console.log(compress("abcabcdede",3)) // "2abcdede"

 

compress는  make함수를 재귀적으로 사용해서 s 문자열을  n개 단위로 압축한 문자열을 반환한다. 

아래서 다시 자세히 설명할 것이다. 

 

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

console.log(chunk("abcabcdede",3)) //  	[ 'abc', 'abc', 'ded', 'e' ]

 

chunk 함수는 s 문자열을 n개 단위로 나눈 배열을 출력하는 재귀함수이다. 

( 짝수인 문자열을 홀수개로 나눈뒤 나머지가 있을때 나머지도 반환해준다)

 

이 함수의 원리는  처음에 받은 s 문자열의 길이가  n과 같거나 적을때까지 계속 slice하는 원리이다. 

 

 

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

console.log(compress("abcabcdede",3)) // "2abcdede"



console.log(chunk("abcabcdede",3)) //  	[ 'abc', 'abc', 'ded', 'e' ] 
//이러한 값을 받았을때 reduce 진행과정을 보자 



처음으로 순회할때 
index = 0
"abc"(현재값) === ""(l) 서로 다르기에
[make(["","",0]), "abc"(현재값), 1] 이된다. 
= ["", "abc", 1]

index = 1
"abc" (현재값) === "abc"(l) 서로 같기에
["", "abc", 2] 가된다.

index = 2
"ded" (현재값) === "abc"(l) 서로 다르기에
[make(["","abc",2],"ded",1]
= ["2abc", "ded", 1]

index = 3
"e" (현재값) === "ded"(l) 서로 다르기에
[make(["2abc","ded",1],"e",1)]
= ["2abcded", "e", 1]

//reduce 끝

//return make(["2abcded","e",1])
= "2abcdede"

 

 

풀이 2)

 

function solution(s) {
  let minLen = s.length; //현재 스트링 길이로 시작한다.

  // 압축하는 문자열 길이를 1개씩부터, s의 반 까지 시도한다.
  top: for (let n = 1; n <= s.length / 2; n++) {
    // 이번 트라이얼의 문자열 길이 초기화한다.
    let curLen = 0;
    for (let i = 0; i < s.length; i += n) {
      // 이번 트라이얼의 길이 n 만큼 테스트를하고, 일치하는 수만큼 카운터로 계산
      // 불일치 시에 다음으로 진행
      let counter = 1;
      while (s.slice(i, i + n) === s.slice(i + n, i + 2 * n)) {
        i += n;
        counter++;
      }
      // 만약 하나도 일치가 없었으면, 테스트했던 문자열의 길이만큼만 더해주고,
      // 일치한 문자열이 하나라도 존재했다면 카운터를 스트링으로 변환 후 길이를 더해줌.
      if (counter !== 1) {
        curLen += n + (counter + "").length;
      } else {
        // 1일경우 그냥 n을 더해주는데, 혹시 맨 마지막에 남은 문자열이 n이하일 경우
        // 남는 수만 더해준다.
        curLen += s.length < i + n ? s.slice(i, i + n).length : n;
      }
      // 현재까지의 최소길이보다 현재길이가 커지는 순간, 다음 트라이얼 시작.
      if (minLen <= curLen) continue top;
    }
    // 여기까지 살아남았으면 이번 길이가 최소길이다.
    minLen = curLen;
  }
  return minLen;
}