[프로그래머스] 문자열 압축

문제 링크

코딩테스트 연습 - 문자열 압축

 

- s의 길이는 1000 이하이다. 즉 O(n^2) 정도의 알고리즘으로 풀 수 있다.

 

- 문자열을 활용한 단순 구현 문제인 것 같다. 카카오 코테 1번인가 2번이었던걸로 기억한다.

function solution(s) {
    if(s.length === 1) return 1
    let answerArr = []
    for(let i = 1; i <= Math.ceil(s.length/2); i++){
        let cnt = 1;
        let compressedString = '';
        for(let j = 0; j < s.length; j+=i){
            const tempSubStr = s.substr(j, i)
            const nextSubStr = s.substr(j+i, i)
            if(tempSubStr === nextSubStr) cnt++
            else{
                compressedString = cnt > 1? compressedString + cnt + tempSubStr : compressedString + tempSubStr
                cnt = 1
            }
        }
        answerArr.push(compressedString.length)
    }
    return Math.min(...answerArr)
}

 

- s의 길이가 1인 경우 알고리즘이 작동하지 않으므로 1을 바로 return한다.

 

- i는 압축할 문자열의 길이이다. 1부터 시작하고, 최대 n/2를 넘지 못한다. 왜냐면 길이의 반이 넘어가면 압축이 불가능하기 때문이다.

 

- 첫 i길이의 substr과 다음 i 길이의 substr을 비교한다. 만약 둘이 일치한다면 압축 횟수인 cnt를 +1 해준다. 압축이 되지 않는다면 현재 substr을 더해주고, cnt를 초기화 하면 된다. 

 

- 각 i 길이로 압축된 문자열은 array에 push해 준다. 그리고 답을 구할 때는 이들을 spread문법으로 펼쳐주어 가장 작은 수를 return해 주면 된다.