[프로그래머스 lev2/JS] 문자열 압축

문제 출처

프로그래머스 lev2 - 문자열 압축

문제

나의 풀이 (실패)

function solution(s) {
  let unit = [];

  for (let i=0; i<s.length; i++) {
    let cnt=Math.floor((s.length-i)/2);
    for (let j=1; j<=cnt; j++) {
      let a = s.slice(i,i+j);
      let b = s.slice(i+j,i+(j*2));

      if (a==b && !unit.includes(j)) {
        unit.push(j);
      }
    }
  }
  console.log(unit);
  let answer = Array.from({length:unit.length}, () => '');

  for (let i=0; i<unit.length; i++) {
    for (let j=0; j<s.length; j++) {
      let a = j+unit[i];
      let b = (j+unit[i])+unit[i];
      let cnt=2;
      // console.log(j, a, b, s.slice(j,a), s.slice(a,b), answer);

      if (s.slice(j,a) === s.slice(a, b)) {
        // while (s.slice(j,a) === s.slice(a, b)) {
        //   j++;
        //   a = j+unit[i];
        //   b = (j+unit[i])+unit[i];
        //   cnt++;
        // }
        if (answer[i].slice(answer.length-(s.slice(j,a).length+1) , answer.length) !== cnt + s.slice(j,a)) {
          answer[i] += cnt + s.slice(j,a);
        }
        j=b-1;
      }

      else if (s.slice(j,a) !== s.slice(a, b)) {
        if (unit[i] > 1) {
          answer[i] += s.slice(j,a)+s.slice(a,b);
        }
        else {
          answer[i] += s.slice(j,a);
        }
        j=b-1;
      }
    }
  }
  console.log(answer);
  
  let min=Number.MAX_SAFE_INTEGER;
  for (let x of answer) {
    if (min > x.length) {
      min = x.length;
    }
  }
  return min;
}

console.log(solution("aabbaccc"));
// console.log(solution("ababcdcdababcdcd"));
// console.log(solution("abcabcdede"));
// console.log(solution("abcabcabcabcdededededede"));
// console.log(solution("xababcdcdababcdcd"));

다른 풀이

같을 때는 진행하고, 다를 때 비로소 넣어주는 게 핵심 아이디어!!

function solution(s) {
  let answer = [s.length]; 
  const maxLen = Math.floor(s.length / 2); // ouptut: 4

  for (let i = 1; i <= maxLen; i++) { // i = 1, 2, 3, 4
    let count = 1; 
    let sub_str = "";
    for (let j = 0; j < s.length; j += i) { 
      const first = s.substring(j, j+i); 
      const second = s.substring(j + i, j + i * 2);
      /* 
      핵심 아이디어 
      1. 같은 단위로 비교를 해. ex) substring(0,1) === substring(1,2) 
      2. 같으면 count++;을 해주되, 바로 그 단위를 넣는 게 아니라 
         다를 때(즉, 같은 단위의 마지막에 왔을 때) 그 단위를 넣고 count도 문자열로 인식해서 넣어. 
         ex) aa이면, 일단 첫번째 a에서는 count++; 해서 2로 만들어주고 
             ab인 시점, 즉 마지막 a에서 비로소 count + 마지막a(1,2) 를 sub_str에 넣어. 
             그러면 aa도 length가 2이지만 2a도 length가 2니까 
             length를 계산하는 데 있어서는 상관이 없으면서도 우리는 배수를 계산할 수 있게 돼. 
      */
      
      /*
      * 문제의 질문은 몇개 단위로 쪼갰을 때가 최소값이냐임. 
      (1개단위일 때? vs 2개단위일 때) -> 
      단위는 i로 컨트롤하고 연산은 마지막 중복 문자열을 계산해주는 방식으로 해결 


      */
      
      /* aabbaccc
      i = 1, j = 0~7
      a a : (0,1) (1,2) count++; | c = 2; 
      a b : (1,2) (2,3) sub_str = "" + 2 + (1,2) | c = 1; 
      b b : (2,3) (3,4) count++; 
      b a : (3,4) (4,5) sub_str = "2 + (1,2)" + 2 + (3,4) | c = 1; 
      a c : (4,5) (5,6) sub_str = "2 + (1,2) + 2 + (3,4)" + (4,5)
      c c : (5,6) (6,7) count++; | c = 2;
      c c : (6,7) (7,8) count++; | c = 3; 
      c   : (7,8) (8,9) sub_str = "2 + (1,2) + 2 + (3,4) + (4,5)" + 3 + (7,8) | c = 1; 
      -> sub_str.length == 7; 

      i = 2, j = 1~7

      ab ba : (1,3) (3,5)  
      bb ac : (2,4) (4,6) 
      ba cc : (3,5) (5,7) 
      ac cc : (4,6) (6,8) 
      cc c : (5,7) (7,9) x여기서 끝 
      cc : (6,8) (8,10) 
      cc : (7,9) (9,11) 

      */
      if (first === second) {
        count++; 
      }
      else {
        if (count === 1) {
          sub_str = sub_str + first; 
        }
        else {
          sub_str = sub_str + count + first; 
          count = 1; 
        }
      }
    }
    answer.push(sub_str.length);
  }
  return Math.min(...answer);
  
  }

console.log(solution("aabbaccc"));
// console.log(solution("ababcdcdababcdcd"));
// console.log(solution("abcabcdede"));
// console.log(solution("abcabcabcabcdededededede"));
// console.log(solution("xababcdcdababcdcd"));

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)];


console.log(solution("aabbaccc"));
// console.log(solution("ababcdcdababcdcd"));
// console.log(solution("abcabcdede"));
// console.log(solution("abcabcabcabcdededededede"));
// console.log(solution("xababcdcdababcdcd"));