2020 KAKAO BLIND RECRUITMENT 문자열 압축 (js)

문자열 압축 (40) 문제 보기

---

문제 이해

조건으로 필요하다고 생각되는 부분만 정리하면 다음과 같다. 

 

  - 문자열에서 같은 값이 연속해서 나타나는 문자를, 그 문자의 개수와 반복되는 값으로 표현한다.
  - 문자가 반복되지 않아 한번만 나타난 경우에 숫자 1은 생략한다. 
  - 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법 찾는다.
  

문제 풀이

  - 1부터 s.length / 2 단위로 자른 결과를 모두 구하고
  - 가장 짧은 결과를 반환한다.

 

요구사항 자체는 간단하기 때문에 이렇게만 생각했다.

 

1개 단위를 2a2b와 같은 형태로 만들 수 있다면,

n개 단위는 slice를 이용해서 구현하면 되는 문제가 되겠구나 싶었기 때문에

우선은 1개 단위를 2a2b와 같은 형태로 만들었다.

const solution = (s) => {
  let compressed = "";
  let current = s[0];
  let count = 0;

  for (let i = 0; i < s.length; i++) {
    if (current === s[i]) {
      // 문자의 모양이 같으면 count ++
      count++;
    } else {
        // 문자의 모양이 다르면 2ab 형태로 추가하고 다음 문자열 탐색을 위해 값 초기화
        // 숫자 1은 생략하기 위해 삼항 연산자를 이용
      compressed += `${count === 1 ? "" : count}${current}`;
      current = s[i];
      count = 1;
    }

    // 마지막까지 탐색했다면 남아 있는 문자열들을 붙여준다.
    if (i === s.length - 1) {
      compressed += `${count === 1 ? "" : count}${current}`;
    }
  }

  console.log(compressed); // 2a2ba3c
};

solution("aabbaccc");

 

이제 이중 for문을 이용하여 비교 문자열을 n개 단위로 잘라줄 차례다.

 

"aabbccc"를 예시로

최초의 문자열 s.slice(0,1) // "a"

최초의 문자열 s.slice(0,2) // "aa"

최초의 문자열 s.slice(0,3) // "aab"

...

 

이제 비교 문자열은 위와 대응하여 다음과 같이 잘려야 한다.

비교 문자열 s.slice(1,2) // "a"

비교 문자열 s.slice(2,4) // "bb"

비교 문자열 s.slice(3,6) // "bcc"

...

 

마지막으로 확인하면 되는 부분은 나머지 문자열 처리이다.

마지막 문자열 s.slice(6,7) // "c"

마지막 문자열 s.slice(6,8) // "c"

마지막 문자열 s.slice(6,9) // "c"

...

1개일 때는 1개니 신경 안써도 되지만 2개, 3개일 때는 나머지 문자열이 남게 된다.

나머지 문자열에 대해서는 자르기 시작하는 문자열 인덱스 + 자르는 수 >= s.length 로 통일할 수 있다.

6+1 >= s.length

6+2 >= s.length

6+3 >= s.length

이렇게 자르는 문자열을 포함한 길이가 전체 문자열 길이를 초과하면 마지막에 따로 추가시켜주기로 한다.

const solution = (s) => {
  const result = [];

  // j는 문자열을 얼마만큼 자를지 결정하는 수
  for (let j = 1; j < s.length / 2 + 1; j++) {
    let compressed = "";
    let current = s.slice(0, j);
    let count = 0;

    for (let i = 0; i < s.length; i += j) {
      // slice(i,i+j) i부터 j개씩 씩 자르기
      const next = s.slice(i, i + j);

      if (current === next) {
        // 이전 문자열의 생김새가 비교 중인 문자열의 생김새와 같으면 count ++ 
        count++; 
      } else {
        // 생김새가 다르면 2a 형태로 추가
        compressed += `${count === 1 ? "" : count}${current}`;
        current = next;
        count = 1;
      }

	  // 나머지 문자열에 대해 처리
      if (i + j >= s.length) {
        compressed += `${count === 1 ? "" : count}${current}`;
      }
    }
    // 압축된 문자열 끼리의 비교를 위해 압축된 문자열의 길이를 추가
    result.push(compressed.length);
  }

  console.log(result); // [ 7, 8, 8, 8 ]
  return Math.min(...result); // 7
};

solution("aabbaccc");