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

제리·2021년 1월 9일
0

프로그래머스

목록 보기
10/25

https://programmers.co.kr/learn/courses/30/lessons/60057

function solution(s) {
    var answer = 1000000;
    
    for(let crypto = 1; crypto <= s.length; crypto++){
        let bfr = ''
        let length = 0
        let cnt = 0
        for(let idx = 0; idx  < s.length; idx+=crypto){
            let str = s.slice(idx, idx + crypto)
            if(idx == 0) cnt = 1
            else if(bfr == str){
                cnt++
            }
            else{
                length += crypto
                if(cnt > 1) length += cnt.toString().length
                
                cnt = 1
            }
            bfr = str
        }
        length += bfr.length
        if(cnt > 1) length += cnt.toString().length
        
        answer = answer > length ? length : answer
    }
    
    return answer;
}

브루투포스로 모든 압축가능한 경우를 다 검사하여 가장 작은 값을 얻었다.
slice함수로 압축될 문자열을 지속적으로 추출했다.
시간복잡도는 O(N^2) 이다.

profile
흐릿한 잉크가 뚜렷한 기억보다 낫다

0개의 댓글