프로그래머스 60057 문자열압축 파이썬

문제링크

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

문자열의 크기는 어떻게 될까?

테케2번 : ababcdcdababcdcd ⇒ 절반인 8개로 압축되면 2ababcdcd
→ N//2까지 압축 가능함
⇒ 압축 범위는 1~N//2

압축이 진행되는 범위는 어디일까?

문자열 전역에서 압축이 일어날수 있음
⇒ 문자열을 훑어야 하는 범위는 N

압축단위가 클수록, 압축문자열의 길이가 길까?

압축길이를 탐색할때 1→ (N//2) 방향으로 하나씩 늘려서 찾는방법과
(N//2) → 1 방향으로 하나씩 줄여서 찾는 방법이 있다.

N//2 → 1 방향으로 탐색할때 큰 단위로 압축된 문자열의 압축문자열이 길까? 에 대해서 생각해봤는데
내생각은 ‘아니다’. 2개 단위로 압축된 문자열보다, 2000개 단위로 압축된 문자열의 길이가 무조건 짧다고 보장하지 못할것이라고 생각했다.

따라서 이 경우에는 1~N//2 사이의 모든 단위를 찾는게 맞다고 판단했다.

소스코드(해설)

def splited_function() :
    temp = []
    i,j = 0, spliter

    while j < (N+1):
        temp.append( s[i:j])
        i += spliter
        j += spliter

    #겹쳐지지않는 단어에 대한 예외처리
    if i != N :
        temp.append(s[i:N])
    return temp

INPUT : 문자열 전체

OUTPUT : 문자열을 1개,2개,3개… (N//2)+1개 씩 짤라서 구분해놓은 리스트

def counting_function() :
    result_temp = ""
    word_temp = temp[0]
    cnt = 1
    idx = 1

    while True:
        if word_temp == temp[idx]:
            cnt += 1
        else:
            if cnt == 1:
                result_temp = result_temp + word_temp
            else:
                result_temp = result_temp + str(cnt) + word_temp
            word_temp = temp[idx]
            cnt = 1
        idx += 1
        if idx == len(temp):
            break

    # 마지막꺼는 안더해져있어서 예외처리
    if cnt == 1:
        result_temp = result_temp + word_temp
    else:
        result_temp = result_temp + str(cnt) + word_temp

    return result_temp

INPUT: splited_function()에서 리턴된 리스트

OUTPUT : 문자열을 최대로 압축시켜놓은 결과문자열

소스코드(전문)

s = "abcd"
#2 : 2ab2cd2ab2cd
#8 : 2ababcdcd

N = len(s)
answer = 1000

def splited_function() :
    temp = []
    i,j = 0, spliter

    while j < (N+1):
        temp.append( s[i:j])
        i += spliter
        j += spliter

    #겹쳐지지않는 단어에 대한 예외처리
    if i != N :
        temp.append(s[i:N])
    return temp

def counting_function() :
    result_temp = ""
    word_temp = temp[0]
    cnt = 1
    idx = 1

    while True:
        if word_temp == temp[idx]:
            cnt += 1
        else:
            if cnt == 1:
                result_temp = result_temp + word_temp
            else:
                result_temp = result_temp + str(cnt) + word_temp
            word_temp = temp[idx]
            cnt = 1
        idx += 1
        if idx == len(temp):
            break

    # 마지막꺼는 안더해져있어서 예외처리
    if cnt == 1:
        result_temp = result_temp + word_temp
    else:
        result_temp = result_temp + str(cnt) + word_temp

    return result_temp

if N == 1 :
    answer = 1
else :

    for spliter in range(1, N//2 +1,1) :

        temp = splited_function()
        result_temp = counting_function()

        answer = min(len(result_temp), answer)
        # print(answer)
    # print(answer)

특이사항

1. 테스트케이스에 길이가 1인 문자열이 있어서 이를 막기위해 N==1 처리를 따로 진행해줬음
2. answer=1000 로 초기화시켜줘서 처음결과가 무조건 갱신되도록 진행
3. result_temp로 나온 결과(압축문자열)을 따로 []에 넣지않고, 바로 길이갱신을 진행