[2020 카카오공채 코딩테스트 1번(문자열 압축) 풀이]

카카오공채 코딩테스트 1번 문제 풀이입니다.

문자열 압축 문제이며 서브 스트링을 반복문을 활용하여 체크하면 됩니다. python의 슬라이싱 기능을 적극 활용하면 되는 문제입니다. 최소단위 1부터 최대단위 문자열길의/2 까지 확인하면 됩니다. 즉 문자가 9개인 문자열이라면 1개 단위부터 4개 단위까지 체크하면 됩니다.

 

모든 단위에 대해서 문자열 압축을 진행한 후 최소값을 찾아야 하기 때문에 모든 케이스를 커버하는 일반적인 문자열 압축 함수를 만들면 되겠습니다. 

문자열의 길이가 문자열에 의해 결정되므로 길이를 입력으로 하는 함수를 만들면 편리합니다. 즉, 입력은 체크 단위, 출력은 압축된 문자열을 하는 함수 모듈을 만들어 사용하면 되겠습니다. 내부 코드 구현은 서브스트링을 특정 구간에 대해서 일치하는지 확인하면 됩니다. 반복문과 슬라이싱 기능을 활용하면 편합니다. 디테일한 슬라이싱 구간 설정과 압축 과정에서 디버깅하기가 까다롭지만 단순하게 생각해보면 답이 나옵니다. 

 

for i in range(n, len(origin_str), n):
        prev_str = origin_str[i-n:i]
        next_str = origin_str[i:i+n]

 

이와 같은 방식으로  단위별로 슬라이싱을 하여 일치 여부를 파악하면 되겠습니다. 슬라이싱 후 압축한 결과를 저장해 나가고 이 루틴을 반복하면 문자열 압축이 종료됩니다. 1번 문제인 만큼 단순하게 해결하는 문제였습니다.

 

문제출처

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

 

풀이코드

origin_str = ""
def solution(s):
    global origin_str
    origin_str = s
    
    if len(origin_str) == 1:
        return 1
    
    check_res_lst= []
    for i in range(1, int(len(origin_str)/2+1)):
        check_res = check(i)
        check_res_lst.append(len(check_res))

    #print(check_res_lst)
    return min(check_res_lst)


def check(n):
    global origin_str
    compress_str = ""
    
    cnt = 1
    for i in range(n, len(origin_str), n):
    
        prev_str = origin_str[i-n:i]
        next_str = origin_str[i:i+n]
        
        if prev_str == next_str :
            cnt +=1
        else:
            if cnt == 1:
                compress_str += prev_str
            else:
                compress_str += str(cnt)+prev_str
                cnt = 1

    # left string    
    if cnt == 1:
        compress_str += next_str                
    else:
        compress_str += str(cnt)+prev_str

    return compress_str