알고리즘 :: 0과1 문자열 압축, 재귀함수, 분할정복

알고리즘 공부하며 배운내용

 

 

문자열 압축

0과 1로 이루어진 문자열이 있다.

다음 규칙으로 압축을 해보자

1. 모든 문자가 1이면 1로 압축
2. 모든 문자가 0이면 0으로 압축
3. 그 외 문자열을 절반으로 나누어
   '( + 압축된 왼쪽 문자열 + 압축된 오른쪽 문자열 + )'로 압축

 

예를 들어

1111 은 1

0000 은 0

1100 은 (10)

 

 

들어오는 값

0과 1로 이루어진 문자열

문자열은 짝수 길이로 주어진다

예)

1111000011110000

 

 

보여줄 값

압축된 문자열 출력

예)

((10)(10))

 

 

핵심 포인트

재귀함수 접근하면,

1이나 0이 반복될 때 정리해줄 베이스 케이스를 정해두고,

반복이 안될 시 왼쪽, 오른쪽 절반씩 재귀함수로 불러준다

=> 이를 분할정복이라고 하나보다

 

코드

// VSCode에서 JavaScript 테스트 하기위한 코드
// 메모장에 테스트 케이스 넣고 compress.txt로 저장했다.
let fs = require('fs')
let input = fs.readFileSync('compress.txt').toString()

function compress(str) {

	// 1이나 0이 반복될 때 해당 문자 리턴
    if([...str].every(s => s === str[0])){
        return str[0]
    }
    
    // 반복 아닐 때 재귀함수 실행
    else {
        return `(${compress(str.slice(0, str.length/2))}${compress(str.slice(str.length/2))})`
    }
}

console.log(compress(input))