[Algorithm🧬] 문자열 압축

문제 / 풀이.py

def solution(s):
    answer = 0
    length = len(s)
    min_length = len(s)

    count = 0
    # 반 이상이 되면 같은 갯수만큼 끊을 수 없으니까 반까지만.
    for j in range(1, int(length / 2) + 1):
        temp_length = length
        # j개만큼 끊어서
        for k in range(0, length - j + 1, j):
            # 현재꺼랑 뒤에꺼랑 같으면 축약 가능.
            if s[k:k + j] == s[k + j:k + 2 * j]:
                # 축약 하면 해당 글자수만큼 길이가 줄어듬.
                count += 1
                temp_length -= j
                # 근데 처음 축약하는 경우는 앞에 숫자가 붙으니까 1 늘어남.
                if count == 1:
                    temp_length += 1
                # 1이 아닌 경우는 그냥 줄어든다고만 생각했는데,
                # 10 100 1000 되면 10a 이렇게 합쳐지니까.. 한자리 더 느는거였네
                # 깔끔하게 풀려면 정규표현식 써서 다시 풀자... 어쩔수없다..
                elif count == 9:
                    temp_length += 1
                elif count == 99:
                    temp_length += 1
                elif count == 999:
                    temp_length += 1
                    
            # 문자열이 반복되지 않으면 count 초기화
            else:
                count = 0
#         print(j, temp_length)
        if min_length > temp_length:
            min_length = temp_length

    return min_length

수업 코드

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

    if (len === 1) return 1;
    
    for(let i = 1; i <= len/2 + 1; i++){ //자르는 크기
        const re = new RegExp(`[a-z]{${i}}`, 'g');
        // console.log(re)
        let 잘린문자열 = s.match(re);
        // console.log(잘린문자열)
        압축문자열 = ''
        let count = 1 //2a2b3c 여기서 앞에 나오는 숫자
        for (j = 0 ; j < 잘린문자열.length; j++) {
            if (잘린문자열[j] === 잘린문자열[j+1]) {
                //aa -> 2a // 뒤에 값을 봐서 같은지!
                count += 1;
            } else if (count === 1) {
                압축문자열 += `${잘린문자열[j]}`;
            } else if (count > 1) {
                // 왜 1보다 크냐면 aa가 1a1a가 아니기 때문!
                압축문자열 += `${count}${잘린문자열[j]}`;
                // 앞 문자열과 뒤 문자열이 다른 경우는
                count = 1;
            }
            // console.log(압축문자열);
        }
        if (len % i !== 0){
            압축문자열 += s.slice(-len % i)
        }
        // console.log(압축문자열);
        answer = Math.min(answer, 압축문자열.length)
    }
    return answer;
}