[python] programmers - 문자열 압축(2020 KAKAO BLIND RECRUITMENT)

오늘은 2020년 카카오 문제를 들고왔다.

 

이 문제를 잘못 이해하고 풀었다가

예제를 꼼꼼히 확인하고

다시 풀었는데

 

이번 기회를 통해

다시 한번 문제를 꼼꼼히 확인하는 것이

얼마나 중요한지 다시 한 번 느끼게 되었다.

 

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

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

 

1. 주요 POINT

 

내가 틀린 원인이었던 부분으로

문자열을 나눌때

반드시 앞에서부터 나눠야한다는 것이었다.

 

마지막 예제를 살펴보면

 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 

이렇게 명시되어있다.

 

1. 실패 코드

 

실패 코드는

위의 경우가 가능하다고

판단하고 만든 코드로

아래와 같다.

def solution(s):
    answer = len(s)
    
    for i in range(1, len(s)//2+1):
        
        ans = ''
        j = 0
        tmp = 1
        tmp_s = ''
        
        while j < len(s):
            if s[j:j+i] == s[j+i:j+2*i]:
                tmp += 1
                tmp_s = s[j:j+i]
                j = j+i
            else:
                if tmp != 1:
                    j += len(tmp_s) - 1
                    ans += str(tmp) + tmp_s
                else:
                    ans += s[j]
                tmp = 1
                tmp_s = ''
                j += 1
        if len(ans) < answer:
            answer = len(ans)
            
    return answer

 

2. 성공 코드

 

미리 길이에 따라

리스트를 만들어 위의 문제를 해결해주었다.

def solution(s):
    answer = len(s)
    
    for i in range(1, len(s)//2+1):
        
        j = 0
        lst = []
        while j < len(s):
            lst.append(s[j:j+i])
            j += i
        
        tmp = 1
        ans = ''
        for j in range(len(lst)):
            if j+1 < len(lst) and lst[j] == lst[j+1]:
                tmp += 1
            else:
                if tmp != 1:
                    ans += str(tmp) + lst[j]
                else:
                    ans += lst[j]
                tmp = 1
            
        if len(ans) < answer:
            answer = len(ans)
            
    return answer

 

마무리

 

요즘 알고리즘을 풀면서

 

*잘못된 부분이 있다면 댓글 부탁드리겠습니다!