문자열 압축

문제 링크

문제 요약

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

Input

• 압축할 문자열

output

• 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이

해결방법

• 압축을 수행하는 zip 함수를 만든다
• 1부터 Math.ceil(length/2)까지 반복한다.
• 압축 후 길이가 가장 적은 결과를 리턴한다.

const zip = (src: string, n: number): number

• 입력된 문자열을 n개 단위로 압축한 결과를 반환한다.

• 자료구조

  • queue: 정규표현식을 이용하여 n개 단위로 나뉜 문자열.
  • stack: 압축된 문자열을 차곡차곡 담을 Stack
  • repeat: stack에 담긴 문자열이 반복된 횟수를 저장할 배열

• queue에 담긴 문자열을 순회한다

  • 현재의 요소와 스택의 마지막에 담긴 요소가 같지 않다면
  • 현재의 요소를 stack에 삽입한다.
  • repeat에 1을 삽입한다.
  • 현재의 요소와 스택의 마지막에 담긴 요소가 같다면
  • repeat의 마지막 요소를 ++한다.

• 스택에 담긴 문자열을 n<요소> 형태로 바꾼다.

  • 이 때 1은 생략한다.
• 바뀐 문자열을 join하고 그 길이를 반환한다.

const zip = (src, n) => {
  var re = new RegExp(`([a-z]{${n}})`)
  const queue = src.split(re).filter(s => s.length)
  const stack = []
  const repeat = []

  queue.forEach(s => {
    if (stack[stack.length - 1] !== s) {
      stack.push(s)
      repeat.push(1)
    } else {
      repeat[repeat.length - 1]++
    }
  })

  const result = stack.map((s, i) => (repeat[i] === 1 ? '' : repeat[i]) + s)
  return result.join('').length
}
function solution(s) {
  let min = s.length

  for (let i = 1; i <= Math.floor(s.length / 2); i++) {
    const result = zip(s, i)
    min = result < min ? result : min
  }

  return min
}