프로그래머스 LV2 문자열 압축

문자열 압축 문제를 풀었지만, refactoring 의 절실함을 느끼고 작성한다. 

 

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

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

 

문제가 카카오 문제라 길고 복잡하니 해당 링크에서 확인하자. 

 

def solution(s):
    if len(s) == 1: return 1 

    lst = []
    for i in range(1, int(len(s)//2)+1):
        tmp = []
        for j in range(0, len(s) - i + 1, i):  
            tmp.append(s[j : j + i])
        lst.append(tmp)

    answer = []
    for i in lst:
        tmp = 1
        tmp_ans = ''
        for j in range(0, len(i)-1, 1):
            if i[j] == i[j+1]:
                tmp += 1 
            else: 
                tmp_ans += (str(tmp) + i[j]) if tmp > 1 else i[j]
                tmp = 1 

        tmp_ans += (str(tmp) + i[-1]) if tmp > 1 else i[-1]

        tmp_ans += s[len(''.join(i)):]    
        answer.append(len(tmp_ans))

    return min(answer)

 

가장 크게 문제점을 느끼는 곳은 총 세 곳이다. 

첫 번째는 

if len(s) == 1: return 1

len(s) == 1인 경우에 대한 별도 예외 처리이고, 

 

두 번째는 

    lst = []
    for i in range(1, int(len(s)//2)+1):
        tmp = []
        for j in range(0, len(s) - i + 1, i):  
            tmp.append(s[j : j + i])
        lst.append(tmp)

쓸대없는 tmp 공간 낭비이며, 

 

세 번째는 

for i in lst:
        tmp = 1
        tmp_ans = ''
        for j in range(0, len(i)-1, 1):
            if i[j] == i[j+1]:
                tmp += 1 
            else: 
                tmp_ans += (str(tmp) + i[j]) if tmp > 1 else i[j]
                tmp = 1 

        tmp_ans += (str(tmp) + i[-1]) if tmp > 1 else i[-1]

for 문내에서 다 처리하지 못하고 마지막에 따로 추가 처리해주는 부분이다. 

 

---

첫 번째,

if len(s) == 1: return 1

별도 처리의 경우 간단하게 해결이 가능하다. 

    for i in range(1, int(len(s)//2)+1):
        tmp = []
        for j in range(0, len(s) - i + 1, i):  
            tmp.append(s[j : j + i])
        lst.append(tmp)

해당 함수내에서 현재 주어지는 text의 중간부분까지만 검사를 함으로써 computational cost를 줄이고 있다. 이 과정에서 만약 text의 길이가 1인 경우에는 

for i in range(1, 1):
...

이 되어 생략되어 버린다. 

이 경우를 방지하기 위하여 

for i in list(range(1, int(len(s)//2)+1)) + [len(s)]

#len(s) = 1인 경우 
for i in list(range(1,1)) + [1]

range를 list 화 하고, 전체 length에 대해 검사하는 항목을 하나 추가하면 코드가 깔끔해진다. 

 

그러나 이 부분은 연산이 몇번 추가되기도 하고, 한편으로는 range를 list 화 시키는 것, 그리고 예외를 알고 있을때만 코딩이 가능하다는 점에서 그냥 예외 하나는 따로 처리해주는 것도 괜찮은 것 같다. 

 

---

두 번째, 

    lst = []
    for i in range(1, int(len(s)//2)+1):
        tmp = []
        for j in range(0, len(s) - i + 1, i):  
            tmp.append(s[j : j + i])
        lst.append(tmp)

는 확실하게 tmp 에 대한 공간낭비가 필요 없다. 

    lst = []
    for i in range(1, int(len(s)//2)+1):
        lst.append([s[j : j + i] for j in range(0, len(s) - i + 1, i)])

2줄로 간소화하며 공간낭비도 줄일 수 있다. 

---

for i in lst:
        tmp = 1
        tmp_ans = ''
        for j in range(0, len(i)-1, 1):
            if i[j] == i[j+1]:
                tmp += 1 
            else: 
                tmp_ans += (str(tmp) + i[j]) if tmp > 1 else i[j]
                tmp = 1 

        tmp_ans += (str(tmp) + i[-1]) if tmp > 1 else i[-1]

이는 매번 비슷한 유형에서 발생하는 이슈이다. 

for 문 내에서 모든 걸 한번에 해결하기 위해서는 기발한 아이디어가 필요하다. 

for i in lst:
    tmp = 1
    tmp_ans = ''
    for a,b in zip(i, i[1:]+['']):
        if a == b:
            tmp += 1 
        else: 
            tmp_ans += (str(tmp) + i[j]) if tmp > 1 else i[j]
            tmp = 1

해당 방법을 통해 list 의 마지막 항을 비교하지 못해서 생기는 문제를 쉽게 해결할 수 있다. 

---

최종 결과 

def solution(s):
    if len(s) == 1: return 1 

    lst = []
    for i in range(1, len(s)//2+1):
        lst.append([s[j : j + i] for j in range(0, len(s) - i + 1, i)])
    
    answer = []
    for i in lst:
        tmp = 1
        tmp_ans = ''
        for a,b in zip(i, i[1:]+['']):
            if a == b:
                tmp += 1 
            else: 
                tmp_ans += (str(tmp) + a) if tmp > 1 else a
                tmp = 1 
        
        tmp_ans += s[len(''.join(i)):]    
        answer.append(len(tmp_ans))
    
    return min(answer)

약 절반으로 길이를 줄일 수 있었다.