[프로그래머스 / 자바스크립트]문자열 압축

 

 

 

---

혹시 틀린 점이나 의견주시고 싶으시면 편하게 말씀해주시면 감사하겠습니다 😀

 

문제 

• 문자열 압축(비손실 압축): 연속된 값의 문자의 개수를 반복되는 값으로 표현

 

조건

• 1은 생략
• 문자열을 1개 이상의 단위로 잘라서 압축
• 이 중 가장 짧은 문자열의 길이를 반환
• 1개 이상 단위 to 주어지는 문자열의 길이 / 2의 범위를 가진다.

 

//! first try
function solution(s) {
  let arrForLen = [];
  let arrForEachUnit = [];

  while (1) {
    let strLen = 1;
    let cnt = 0;
    let tempStr = "";

    for (let q = 0; q < s.length; q += 1) {
      for (let t = 0; t < s.length; t += strLen) {
        if (s[t] !== s[t + 1]) {
          // cnt++;

          if (cnt === 1) {
            tempStr += s.slice(t, t + 1);
          } else {
            tempStr += cnt + s.slice(t, t + 1);
          }

          arrForLen.push(tempStr.length);
          cnt = 0;
          tempStr = "";
        } else {
          if (s.slice(q, t + 1)) {
            cnt++;
          }
        }
      }
      strLen++;
      arrForEachUnit.push(arrForLen.join(""));
    }
    if (strLen > s.length / 2) break;
  }

  console.log(arrForLen);
}

 

첫 시도는 1단위로 압축까지는 구현을 할 수 있지만, 2 단위부터 어떻게 비교를 해야 할지 방법이 잘 떠오르지 않았다.

slice를 이용해서 단위별로 나뉜 문자를 비교를 해줘야겠다고 생각을 했지만, for문이 순회하면서 덩달아 같이 문자열을 알맞게 잘라줘야 되는지 아이디어가 떠오르지 않았다.

 

정해진 시간이 종료되고 구글링을 통해, 그에 관한 힌트를 얻어 적용해 보았다!

 

적용한 코드는 아래에 있다.

 

//! submit code
function solution(s) {
  let arrForLen = [];

  for (let q = 0; q < s.length; q += 1) {
    let strLen = q + 1;
    let cnt = 1;
    let tempStr = "";

    for (let t = 0; t < s.length; t += strLen) {
      let currentStr = s.substring(t, t + strLen);
      let nextToCurrentStr = s.substring(t + strLen, t + strLen + strLen);

      if (currentStr === nextToCurrentStr) cnt++;
      else {
        if (cnt !== 1) {
          tempStr += cnt + currentStr;
        } else {
          tempStr += currentStr;
        }
        cnt = 1;
      }
    }
    arrForLen.push(tempStr.length);
    if (strLen > s.length / 2) break;
  }
  return Math.min(...arrForLen);
}

 

currentStr와 nextToCurrentStr 서로 비교할 변수를 만든 후, substring을 이용해 초기화 및 할당을 해주었다.

다음, 두 변수를 비교를 조건으로 두어서 문제를 풀었다.

 

시간복잡도는 O(n^2)이다!