[프로그래머스 Lv.2] - 문자열 압축 (2020 KAKAO BLIND RECRUITMENT)

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

프로그래머스

[문제 요약]

 문자열 s를 압축하려고 한다.

동일한 개수로 잘랐을 때 연속으로 동일한 토큰이 존재한다면 압축 가능

가장 짧게 압축했을 때의 길이를 return 하게 하라

 

[단순 무식한 방법]

1. len(s)/2의 길이까지 직접 토큰을 나눠 봄

2. 각각의 케이스에서 앞 뒤 토큰을 비교

  2-1. 만약 똑같다면 해당 토큰을 기억해두고 앞에 붙일 숫자를 늘인다

  2-2. 만약 다르고

    2-2-1. 앞 토큰이 처음 등장한 친구라면 정답에 해당 토큰을 붙여놓는다

    2-2-2. 앞 토큰이 이전에 등장했던 친구라면 정답에 토큰이 등장한 횟수 + 토큰을 붙여놓는다

  2-3. 정답의 길이가 그 전 정답의 길이보다 작다면 저장

3. 정답의 길이 리턴

 

def solution(s):
    answer = 9999999
    if len(s) ==1:
        return 1
    for i in range(1,int(len(s)/2)+1): # i개 단위로 잘라 압출
        temp = []
        fin = ''  
        for j in range(0,len(s),i): #자르는 과정
                try:
                    temp.append(s[j:j+i])
                except:
                    temp.append(s[j:])     
        mul = 1
        key = ''
        temp.append('0')
        for k in range(len(temp)-1):

            if temp[k] == temp[k+1]:
                key = temp[k]  
                mul+=1
            else:
                if mul == 1:
                    fin += temp[k]
                else:
                    fin += str(mul)+key
                    mul=1
                
        if answer > len(fin):
            answer = len(fin)
    return answer

 

코드 다 짜놓고 디버깅 하지말고

차례차례 디버깅하는 습관을 들이자..

시간이 훨 배 더 걸린다

 

[다른분들 코드]

def compress(text, tok_len):
    words = [text[i:i+tok_len] for i in range(0, len(text), tok_len)]
    res = []
    cur_word = words[0]
    cur_cnt = 1
    for a, b in zip(words, words[1:] + ['']):
        if a == b:
            cur_cnt += 1
        else:
            res.append([cur_word, cur_cnt])
            cur_word = b
            cur_cnt = 1
    return sum(len(word) + (len(str(cnt)) if cnt > 1 else 0) for word, cnt in res)

def solution(text):
    return min(compress(text, tok_len) for tok_len in list(range(1, int(len(text)/2) + 1)) + [len(text)])

zip() 함수 -> iterable 객체를 인자로 받고,

각 객체가 담고 있는 원소를 튜플의 형태로

차례로 접근할 수 있는 반복자를 반환

 

병렬처리가 가능하다,,