구현 - 문자열 압축

문자열 압축

한번 풀었던 문제라 간단하게 해결하고 싶었으나 엄청나게 해맸다. 

 

• ababcdcdababcdcd
• 2ab2cd2ab2cd : 2개 단위
• 2ababcdcd : 8개 단위
• 문자열을 1개 이상 단위로 압축 할 때 가장 짧은 것의 길이를 return
• 문자열은 제일 앞부터 정해진 길이만큼 잘라야 한다. 따라서 주어진 문자열을 x/ ababcdcd / ababcdcd 로 자르는 것은 불가능
• 한번만 나타난 경우 1 은 생략

 

해당 문제의 해결 골자는 다음과 같다. 

반복이 될 수 있는 경우는 글자 1개 ~ 총 글자 // 2 이다. 

총 글자 // 2 를 넘어선 순간 반복하면 총 글자 수를 넘어가서 반복이 불가능하다. 

 

문제에서 구하고자 하는 답은 "반복 하는 경우 중 가장 글자 수가 적은 경우" 이다. 

즉 반복이 될 수 있는 경우는 글자 1개 ~ 총 글자 // 2  중 가장 총 글자 수가 적은 경우를 찾아야 한다. 

 

앞 뒤 반복을 확인하며 다음의 경우가 발생한다. 

1) 몇번 반복되었느냐에 단어의 수가 결정된다. 

2) 반복이 멈추는 경우가 앞선 반복 단어의 수가 결정되는 순간이다. 

3) 반복을 확인 할 때 앞 단어 그 다음 단어를 비교해서 결정하다 보니 최종 반복 단어는 비교할 다음 단어가 없어 누락될 수 있다. 

구현에서 이를 고려해줘야 한다. 

4) 반복 수에서 남는 글자들은 나열되므로 총 단어수 % 반복 수로 그 수를 더해준다.  

 

문제 풀이 

S = input().rstrip()

lst = []

for i in range(1, len(S)//2 +1):
    first = S[0:i]
    ans = 0
    cnt = 0
    for j in range(i, len(S) -i+1, i):
        next_ = S[j:j+i]
        if first == next_:
            cnt += 1 
        else:
            if cnt != 0:
                ans += (i+1)
                cnt = 0 
            else:
                ans += i

        first = next_
    ans += (i+1) if cnt != 0 else i
    ans += (len(S)%i)
    lst.append(ans)

print(lst)

짧지만 가독성도 떨어지고 생각보다 예외처리 및 구현에 어려움을 겪었다. 

 

아래는 한창 코딩테스트 감이 좋을 때 풀었던 풀이이다. 

 

개선된 풀이방법

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)

문제를 zip 으로 풀 생각은 해봤으나 반복되는 수도 바뀌고 항목을 접근 할 때 어떻게 반복 되는 글자들을 묶어줄지 아이디어가 안떠올랐는데, 그 당시의 나는 떠올랐었던듯 하다. 다만 당시에는 구하고자 하는 정답이 길이임을 고려하여 길이만 처리했으면 되는데 굳이 문자열을 만들고자 했었다. 하지만 사실 반복되는 횟수가 2자리를 넘어갈 수도 있기때문에 이는 문자열을 만드는 것이 유리한 문제였다. 

 

zip 으로 풀때의 장점은 총 두가지이다. 

1) 코드의 readability 가 높다. 

2) 최종 case 에 대한 처리를 따로 안해줘도 되게 짤 수 있다. - 하지만 이는 경우에 따라 다르긴하다. 

 

정리하자면 리스트를 돌면서 내부의 원소끼리 비교하는 등의 처리를 할 때 처음이나 마지막에 처리가 잘 되는지 않되는지등의 파악을 항상 해주어야 한다. 

이번 경우에는 앞 원소와 뒤 원소를 비교하고 다른 경우 앞 원소의 개수를 반영하는 식으로 하다보니 마지막 원소의 개수가 반영이 되지 않았었다. 

 

※ 부록

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)])


    result = 10e9
    
    for data in lst:
        cnt = 0
        ans = 0 
        for first, second in zip(data, data[1:] + [' ']):
            if first == second:
                cnt += 1 
            else: 
                ans += (len(first) + 1) if cnt != 0 else len(first) 
                cnt = 0
        result = min(ans, result)
    
    return result

위 풀이법으로 개수만 구해서 풀어보려 했으나 많은 경우 실패 

비교책이 한개 더 많아져서 첫번 째 겪었던 문제와 유사한 문제 발생. 

 

또한 반복된 문자가 10개 넘어가면 반복 문자 길이 + 1 에서 1 이 2 가 되어야 한다. 

즉, 해당 문제는 문자열로 해결하는 것이 가장 지혜롭다. 

 

두 가지 비교 

rest = len(S) % len(first) 
if len(ans) + rest< result:
    result = len(ans) + rest

ans += S[len(''.join(data)):]

%가 꽤 빠를 줄 알았는데 비슷하다.