[프로그래머] - lv2 문자열 압축 JavaScript

프로그래머스 lv2 문자열 압축

레벨: 2

언어: JavaScript

---

문제 풀러 가기

문제 설명

간단한 예로 "aabbaccc"의 경우 "2a2ba3c"(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, "abcabcdede"와 같은 문자열은 전혀 압축되지 않습니다. "어피치"는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, "ababcdcdababcdcd"의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 "2ab2cd2ab2cd"로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 "2ababcdcd"로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, "abcabcdede"와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 "abcabc2de"가 되지만, 3개 단위로 자른다면 "2abcdede"가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

입력 값

• 압축해야 하는 문자열
  • 0 < 문자열 길이 < 1001
  • 소문자로만 구성

출력 값

• 최대 압축한 문자열 길이 중 가장 작은 문자열 길이

📑풀이 아이디어

• 문자열 압축은 1~ 문자열 s의 길이 / 2까지 할 수 있다.
• 1부터 최대길이 (s.length /2)까지 완전 탐색하여 찾는다.

📋풀이 코드

function solution(s) {
  let answer = s.length;

  for (let i = 1; i <= parseInt(s.length / 2); i++) {
    let str = "";
    let cnt = 1;
    let tempStr = s.substr(0, i);
    let idx = 0;

    for (idx = i; idx <= s.length; idx += i) {
      let nextStr = s.substr(idx, i);

      if (tempStr === nextStr) {
        cnt += 1;
      } else {
        if (cnt === 1) str = str + tempStr;
        else str = str + cnt + tempStr;

        cnt = 1;
        tempStr = nextStr;
      }
    }
    if (cnt === 1) str = str + tempStr;
    else str = str + cnt + tempStr;
    answer = Math.min(answer, str.length);
  }

  return answer;
}

코드 라인별 설명

for (let i = 1; i <= parseInt(s.length / 2); i++)

• i는 압축하는 문자열의 길이이다.
• i의 최대 값은 s.length 길이의 반이다.

let str = ""; //압축한 문자열 변수 저장
let cnt = 1; //압축한 횟수
let tempStr = s.substr(0, i); //압축하는 기준 문자열
let idx = 0; // s 문자열에서 압축하기 위한 문자열의 위치를 나타내는 변수

for (idx = i; idx <= s.length; idx += i)

• idex는 s문자열에서 압축하기 위한 문자열의 위치를 나타낸다.

let nextStr = s.substr(idx, i);

• nextStr 은 idx의 위치에서 i길이만큼의 문자열을 가져온다.
• tempStr과 비교하는 문자열이다.

if (tempStr === nextStr) { //두번째 for문 안의 코드
  cnt += 1;
} else {
  if (cnt === 1) str = str + tempStr;
  else str = str + cnt + tempStr;
}

• tempStr과 nextStr이 같으면 압축이 가능함으로 cnt를 +1 한다.
• 같을 때 cnt가 1이면 압축 가능한 문자가 없기에 기준 문자열 tempStr을 str 뒤에 붙인다.
• cnt가 1이 아닐 때는 압축이 cnt만큼 되는 문자열이니 str 뒤에 압축 수(cnt)+ tempStr을 붙인다.

cnt = 1;
tempStr = nextStr;

• cnt를 다시 1로 최기화한다.
• tempStr(기분 문자열)은 압축이 불가능한 nextStr을 넣어 nextStr을 기준으로 압축 가능한지 찾는다.

//두번째 for문이 끝난 후의 코드
if (cnt === 1) str = str + tempStr; 
else str = str + cnt + tempStr;

answer = Math.min(answer, str.length);

• 두 번째 for문이 끝났을 때 뒤에 문자열이 저장이 안 된 부분을 str에 넣어주는 코드이다.
• 그리고 answer에는 문자열의 길이를 비교하여 최저 값을 answer에 할당한다.

---

문제를 어떤 방식으로 접근해야 하는지 고민을 많이 했고 결국은 다른 사람의 풀이를 보았다.

풀이를 보고 나서도 이해하는데 어려움이 있었다. 매일 lv1 만 풀다 보니 lv2는 좀 어려움 감이 있다.

다양한 문제를 풀어보고 더 연습을 해봐야겠다.