[Algorithm] 문자열 압축

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

해결 과정

처음 풀었을 때는 한 시간 정도 걸렸는데, 기본 케이스에서 부터 틀렸음. 반례 계속 고치려다가 더 꼬이는 것 같아서 다음 날 새롭게 다시 시작함. (이 때는 테케 해결까지 50분 가량 소요) 어제 생각했던 IDEA 기반으로 이번에는 finalStr에 직접 문자를 추가하고 길이를 계산하는 식으로 변경. (문제에서 설명하는 그대로 코드에 구현) 이번에도 print문 찍어가면서 "aabbaccc" 해당 케이스가 제대로 나오는지 따져가며 풀었음. 마지막에는 테스트 케이스 5번 런타임 에러가 났는데, 런타임 에러 날 곳이 어딘지 찾다가 s길이가 1인 경우 for문을 안들어가고 min([])을 하고 있었음. 제일 위에 s 길이가 1인 경우 빼줘서 해결.

나의 풀이

def solution(s):
    candidates = []
    if len(s) == 1:
        candidates.append(1)
    for unit in range(1, len(s) // 2 + 1):
        temp = ""
        count = 0
        finalStr = ""
        for i in range(len(s) // unit):
            element = s[i * unit:(i + 1) * unit]
            if temp == "":
                temp = element
                count = 1
                continue
            if temp == element:
                count += 1
            elif temp != element:
                if count > 1:
                    finalStr += str(count) + temp
                elif count == 1:
                    finalStr += temp
                temp = element
                count = 1
        if count > 1:
            finalStr += str(count) + temp
        elif count == 1:
            finalStr += temp
        length = len(finalStr) + (len(s) % unit)
        candidates.append(length)
    return min(candidates)

주석 있는 풀이

def solution(s):
    candidates = []
    # s의 길이가 1일 때 처리 -> 안해주면 테스트 케이스 5번 런타임 에러
    if len(s) == 1:
        candidates.append(1)
    for unit in range(1, len(s) // 2 + 1):  # 길이 6이면 1, 2, 3 살피기
        # temp = s[0:unit]
        temp = ""
        count = 0
        finalStr = ""
        # unit 단위 별로 하나 씩 돌기
        for i in range(len(s) // unit):
            element = s[i * unit:(i + 1) * unit]  # 보고 있는 대상
            # print("element", element, "temp", temp, "count", count)
            if temp == "":  # 첫번째 원소면 바로 temp에 넣기
                temp = element
                count = 1
                continue

            if temp == element:
                count += 1

            elif temp != element:
                if count > 1:  # 같은 개수가 2개 이상이면
                    finalStr += str(count) + temp
                elif count == 1:  # 같은 개수가 1개면
                    finalStr += temp

                temp = element
                count = 1
        # 마지막 나왔을 때, temp, count에 있는 것 추가해주기
        if count > 1:
            finalStr += str(count) + temp
        elif count == 1:
            finalStr += temp

        length = len(finalStr) + (len(s) % unit)  # 나머지 있는건 바로 더하기
        candidates.append(length)
        # print("candidates", candidates, "finalStr", finalStr, '\n')
    return min(candidates)

# print(solution("aabbaccc"))

다른 풀이 참고하고 리팩토링한 코드

def solution(s):
    candidates = [len(s)]
    for unit in range(1, len(s) // 2 + 1):
        temp = ""
        count = 0
        finalStr = ""
        for i in range(0, len(s), unit):
            element = s[i:i + unit]
            if temp == element:
                count += 1
            elif temp != element:
                if count > 1:
                    finalStr += str(count) + temp
                elif count == 1:
                    finalStr += temp
                temp = element
                count = 1
        if count > 1:
            finalStr += str(count) + temp
        elif count == 1:
            finalStr += temp
        length = len(finalStr)
        candidates.append(length)

    return min(candidates)

주석 있는 풀이

def solution(s):
    candidates = [len(s)] # len(s) 넣어놓음으로써 다음 두 줄 제거
    # if len(s) == 1:
    #     candidates.append(1)
    for unit in range(1, len(s) // 2 + 1):
        temp = ""
        count = 0
        finalStr = ""
        # for i in range(len(s) // unit):
        #     element = s[i * unit:(i + 1) * unit]
        for i in range(0, len(s), unit): # range(, , step) 활용함으로써 윗 두 줄 변경
            element = s[i:i + unit] # 이 부분도 깔끔하게 정리 완료
            # if temp == "": # 이건 어차피 없었어도 됨. count = 0, elif로 가는 로직
            #     temp = element
            #     count = 1
            #     continue
            if temp == element:
                count += 1
            elif temp != element:
                if count > 1:
                    finalStr += str(count) + temp
                elif count == 1:
                    finalStr += temp
                temp = element
                count = 1
        if count > 1:
            finalStr += str(count) + temp
        elif count == 1:
            finalStr += temp
        # length = len(finalStr) + (len(s) % unit) # 이것도 어차피 없었어도 됨. 
        # 문자열 slicing 할 때 ("aggs"[1:100] 이런 것도 가능)
        length = len(finalStr)
        candidates.append(length)

    return min(candidates)

다른 풀이

좋아요 제일 많이 받은 첫 풀이

def compress(text, tok_len):
    words = [text[i:i + tok_len] for i in range(0, len(text), tok_len)]
    res = []
    cur_word = words[0]
    cur_cnt = 1
    for a, b in zip(words, words[1:] + ['']):
        if a == b:
            cur_cnt += 1
        else:
            res.append([cur_word, cur_cnt])
            cur_word = b
            cur_cnt = 1
    return sum(
        len(word) + (len(str(cnt)) if cnt > 1 else 0) for word, cnt in res)


def solution(text):
    return min(
        compress(text, tok_len)
        for tok_len in list(range(1,
                                  int(len(text) / 2) + 1)) + [len(text)])

다른 풀이들 살펴보면 IDEA는 다 비슷하다. 역시나 이런 문제는 구현, IDEA 생각해내고 그것을 실제 코드로 구현하는 연습을 많이 하는게 맞다.

IDEA

런타임에러 -> 특수한 케이스가 있는지, for문 안들어가서 원하는 곳에서 원하는 답 못 구하는 경우 있는지 살피기.

 

for 문 내에서 range든, 문자열 slicing이든, 

• range는 range(시작숫자, 종료숫자, step)의 형태로 리스트 슬라이싱과 유사합니다.
• range의 결과는 시작숫자부터 종료숫자 바로 앞 숫자까지 컬렉션을 만듭니다.
• 시작숫자와 step은 생략가능합니다.

이 문제에서는 step을 활용하면 가독성 좋은 코드 작성 가능.

 

문자열 slicing할 때, 존재하지 않는 번호 넣어도 된다.

ex) "abcdef"[:100] -> 이러면 알아서 "abcdef"가 도출됨.

여기서 런타임에러 나는 줄 알고 코드 구현할 때 생각을 더 해야 했음.