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

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

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

# 2020 카카오 블라인드 코딩테스트 1차 문제이다.

# 단순 구현문제이다. 생각보다 쉬웠는데 정답률이 25.9%여서 놀랐다.

 

# 일단 1번문제이기도 하고 처음에 문제를 볼땐, 완전 탐색을 생각해서 시간초과가 나지 않을 것 같으면

   짜보는 게 좋은 것 같다. (열심히 짜놓고 시간초과 나면 손해긴 하지만..)

 

# 문자열을 잘랐을 때 나오는 부분의 최대 길이는 len(s) // 2이다.

     (길이 16짜리를 자른다고 하면 길이 8짜리 2개가 최대이기 때문이다,  s의 절반길이를 넘는

     개수 단위로 자르면 뒤의 남은 것들로는 압축할 수 없으므로 길이가 길어지게 된다.)

  따라서 1개부터 len(s) // 2개까지 반복문을 돌며 다 잘라보면서 확인하는 식으로 진행했다.

 

1. 처음 target을 s[ : i]로 잡아준다. answer을 초기화해주고 cnt도 1로 설정해준다.

   반복문을 (i, len(s), i)로 돌며 new_s = s[j : j+i]로 설정해주고 target이랑 new_s를 비교해준다.

      (new_s는 자르고자 하는 길이 i로 자른 s의 부분문자열이다.)

 

2. target이랑 new_s가 같으면 cnt를 1증가시켜주고 다르면 answer에 target을 더해줘야하는데

    여기서 cnt가 1이면(한 번 반복되면) 무시하라고 했으므로 cnt가 1이 아닐 때만 answer에

    cnt+target을 더해준다. new_s와 target이 다르면 target을 new_s로 바꿔주고 cnt도 1로 설정해준다.

 

3. s의 끝까지 확인한 뒤 target이 남아있으면 anser에 더해준다.

   이걸 1부터 len(s)//2 까지 모두 자르면서 answer의 길이와 dab중 작은 값을 dab에 넣어준다.

 

4. s 길이가 1이면 1을 return하고 아니면 1~3과정을 거친 후 dab을 return해준다.

    (dab의 초기값은 그냥 s의 길이가 최대 1000이어서 2001로 잡았는데, 그냥 아예 큰수로 잡아도 상관없다)

 

def solution(s):
    if len(s) == 1:
        return 1
    mx = len(s) // 2
    dab = 2001
    for i in range(1, mx+1):
        answer = ''
        target = s[ :i]
        cnt = 1
        for j in range(i, len(s), i):
            new_s = s[j: j+i]
            if new_s == target:
                cnt += 1
            else:
                if cnt == 1:
                    answer += target
                else:
                    answer += str(cnt) + target
    
                target = new_s
                cnt = 1
            
        if cnt == 1:
            answer += target
        else:
            answer += str(cnt) + target
            
        dab = min(dab, len(answer))
        
    return dab

(프로그래머스 level: 2)

 

# 5월에 한번 푼 문제지만, 이번에 아예 코드지우고 새로 풀었다.

   저번에 짠 코드보다 빠른 코드를 짜서 뭔가 발전한 것 같아 뿌듯하다!