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

해당 포스팅은 프로그래머스 문자열 압축 풀이를 다룬다. 문제 링크
코드는 Javascript로 작성하였으며 완전탐색으로 풀이하였다.

풀이

풀다가 계속 무한 루프 돌아서 프로그래머스의 질문방에 올라온 풀이를 보았던 문제였다...ㅜ 코테 볼 때마다 느끼지만 완전탐색 구현 능력이 아직 너무 부족하다...

문자를 각 단위로 잘라서 압축했을 때 가장 짧은 경우의 길이를 리턴해야 하는 문제이다. 모든 경우를 탐색해야 하므로 완전탐색으로 풀이하면 된다. 단위가 가장 큰 경우는 문자열의 절반길이이므로(2'문자열 절반'), 문자열 길이 절반까지 loop를 돌리면 된다.

Pseudo Code

function solution(s) {
  압축한 문자열 길이 answer = s.length;

  // 문자열 길이 절반만큼 loop
  for (i = 1; i <= Math.floor(s.length / 2); i++) {
      // 변수 초기화
      압축한 문자열 sentence = '';
      현재 탐색하는 인덱스 idx = 0;
      // idx가 문자열을 전부 탐색할 때까지 loop
      while (idx < s.length) then
          압축한 횟수 cnt = 1;
          while(현재 단위 문자열 === 그 다음 문자열) then
              cnt += 1; // 압축되므로 횟수 += 1
              idx += i; // 인덱스를 단위만큼 이동

          if (cnt > 1) 즉 압축된 문자열이 있을 시 then
              sentence += cnt; // 압축된 횟수 더하기

          sentence += 단위 문자열 str;
          idx += i; // 그다음 탐색할 문자열로 이동하기 위해 단위만큼 이동

      // 압축한 문자열 길이가 현재 answer보다 작을 시 작은 값으로 업데이트
      answer = Math.min(answer, sentence.length);
  	}
  	return answer;
  }

전체 코드

function solution(s) {
    let answer = s.length;
    
    for (let i = 1; i <= Math.floor(s.length / 2); i++) {
      	let sentence = "";
        let idx = 0;

      	while(idx < s.length) {
           let cnt = 1;
           while (s.slice(idx, idx+i) === s.slice(idx+i, idx+i+i)) {
                 cnt++;
                 idx += i;
           }
          
           if(cnt > 1) {
                sentence += cnt;
           }
           const str = s.slice(idx, idx+i);
           sentence = sentence + str;
           idx += i;
        }
        answer = Math.min(answer, sentence.length);
    }
    return answer;
}