2020 KAKAO BLIND_ 문자열 압축

문제:

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

Wrong way

def slice_str(s, num):
    
    tmp = []
    result = []
    cnt = 0
    
    for i in range(0, len(s), num):
        now = s[i:i+num]
        if now == tmp:
            cnt += 1
            if cnt == 1:
                result.append(str(cnt))
        else:
            result.append(now)
            cnt = 0
            
        tmp = now
        
    result = ''.join(result)
    return result


def solution(s):
    
    min_size = len(s)
    now_size = -1
    
    k_max = len(s) // 2
    k_len = 1
    
    while k_len <= k_max:
        
        now_size = len(slice_str(s, k_len))
        now_size = min(min_size, now_size)
        
        min_size = now_size
        k_len += 1

    return now_size

구현 방법

1. 문자열을 n개 단위로 자른다.

"aabbaccc" 의 경우

n	자른 결과
1	a/ a/ b/ b/ a/ c/ c/ c
2	aa/ bb/ ac/ cc
3	aab/ bac/ cc
4	aabb/ accc
5	aabba/ ccc (불가능)

n은 최대 len(s) / 2

2. slice_str 함수 구현

   • n개 단위로 문자열 s를 순회하면서 이전 문자열과 현재 문자열과 같다면 count

3. solution(s) 함수 구현

   while k_len <= k_max: 범위에서 slice_str(s, k_len)의 결과값과 min_size(이전 결과값) 중 더 길이가 작은 숫자를 now_size에 저장

   return now_size

채점 결과

정확성: 68.0
합계: 68.0 / 100.0

Correct way

def slice_str(s, num):
    
    before = []
    result = []
    cnt = 1
    flag = False
    
    for i in range(0, len(s), num):
        now = s[i:i+num]
        
        if now == before:
            cnt += 1
            flag = True
        
        else:
            if cnt != 1:
                result.append(str(cnt))
                flag = False
            result.append(now)
            cnt = 1
            
        before = now
    
    if flag:
        result.append(str(cnt))
            
    result = ''.join(result)

    return result


def solution(s):
    
    if len(s) in [1,2]: return len(s)
    
    max_size = len(s)
    now_size = -1
    
    k_max = len(s) // 2
    k_len = 1
    

    while k_len <= k_max:
        
        now_size = len(slice_str(s, k_len))
        now_size = min(max_size, now_size)
        
        max_size = now_size
        k_len += 1


    return now_size

반례 찾는데 오랜 시간이 걸렸다.
역시 반례 찾는게 제일 어려운것 같다 후,,,🤯🥲

반례

Case number	입력	출력
1	"a"	1
2	"aaaaaaaaaa"	3
3	"aaaaaaaaaabbbbbbbbbb"	6

• Case number 1

  예외처리

  if len(s) in [1,2]: return len(s)

• Case number 2

  내가 한 가장 큰 실수

for i in range(0, len(s), num):
        now = s[i:i+num]
        if now == before:
            cnt += 1
            if cnt == 1:
                result.append(str(cnt))
        else:
            result.append(now)
            cnt = 0
            
        before = now

이렇게 일단 이전 문자열 조각과 현재 문자열 조각이 같을 경우엔 몇번 중복되는지는 염두하지 않고 1을 넣어줬다.

aaaaaabbbbb 이런 경우엔 len("5a5b" ) == len("a5b5") == len("a1b1") 이런 식이기때문에 1을 넣어줘도 상관이 없다.

하지만 10번 이상 중복되는 경우 갯수를 문자열로 나타냈을 때
`len("10a10b" ) == len("a10b10") != len("a1b1") 이런 경우와 같이 글자수가 달라진다.

때문에 flag를 넣어서 예외처리를 해줬다.

• Case number 3

  slice_str 함수에서 count 변수 초기화를 0으로 해줘서 n개를 n-1개로 세는 문제가 있었다.

  그래서 count 변수를 1로 초기화하는걸로 수정해주었다.

채점 결과

정확성: 100.0
합계: 100.0 / 100.0

🥴