프로그래머스 Lv2 | 2020 KAKAO BLIND RECUITMENT | 문자열 압축

https://school.programmers.co.kr/learn/courses/30/lessons/60057?gad_source=1&gad_campaignid=22199869887&gbraid=0AAAAAC_c4nDRnLcdW5pfc_L8ay5k5GtDz&gclid=CjwKCAjwvO7CBhAqEiwA9q2YJbn8g3uU5ynefiaRrs65vrzEvwxuWyBu9ikUQDfmOJJ79-3OPMuXsBoCgF0QAvD_BwE

프로그래머스

 

 

 

 

 

---

최적화한 풀이

모든 정보를 저장할 필요가 없지 않았는가.. 바로 직전 것만 확인하면 되었던 건데 왜 ..

def compress(s, num):
    cnt = 1
    prev = s[:num]
    compress = ""
    
    # 이전 문자에 대해서만 더함
    for i in range(num, len(s), num):
        curr = s[i:i+num]
        
        if curr == prev:
            cnt += 1
        
        else:
            if cnt > 1: # 바로 직전까지 prev가 이어져 왔었음 
                compress += str(cnt) + prev
            else: # 오직 하나만 이어지는 상태
                compress += prev
            prev = curr
            cnt = 1
    
    # 맨 마지막에서 처리하기
    if cnt > 1: # 바로 직전까지 prev가 이어져 왔었음 
        compress += str(cnt) + prev
    else: # 오직 하나만 이어지는 상태
        compress += prev
    
    return compress
    

def solution(s):
    # 주의사항: 압축이 된다고 해서 압축하는게 항상 짧아지는 것은 아니다.
    # 주의사항: 문자열은 제일 앞부터 정해진 길이만큼 잘라야 한다.
    
    answer = len(s)
    for i in range(1, len(s)//2+1): # 최소 2개무터 전체 길이의 반까지 압축 가능
        answer = min(len(compress(s,i)),answer)

    return answer

 

첫 시도

답은 맞긴 맞았는데 ,, dict로 처리하는게 최선이 아니었을 것 같다

실제로 abab가 2개의 뭉텅이에서 보인다면 그걸 제대로 저장하는 형식은 아니었기 떄문에 앞에것만 저장했음

def compress(s, num):
    compression = {}
    for i in range(0,len(s),num):
        if i + num <= len(s):
            tmp = s[i:i+num]
            if tmp in compression:
                if compression[tmp][0] + num == i:
                    compression[tmp][0] = i
                    compression[tmp][1] += 1
            else:
                compression[tmp] = [i,1]
    
    for key, value in compression.items():
        for i in range(value[1],1,-1):
            s = s.replace(key*i,str(i)+key)
        
    return s
    

def solution(s):
    # 주의사항: 압축이 된다고 해서 압축하는게 항상 짧아지는 것은 아니다.
    # 주의사항: 문자열은 제일 앞부터 정해진 길이만큼 잘라야 한다.
    
    comp_list = [s] # 압축 길이 1일 때
    for i in range(1, len(s)//2+1): # 최소 2개무터 전체 길이의 반까지 압축 가능
        comp_list.append(compress(s,i))
    answer = 1000
    
    for c in comp_list:
        if len(c) < answer:
            answer = len(c)

    return answer