[프로그래머스] 2020 카카오 문자열 압축

문제

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

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

---

풀이

알고리즘 카테고리에서 어느 것에 해당하는 것인지 생각해 보았는데 (해시, 정렬, 동적계획법 등) 적절한 것이 떠오르지 않아 그냥 짜보기로 했다.

구현력을 시험하는 문제같기도 하다.

생각한 방법은 다음과 같다.

 

ex) aabbacccc

1. 1~문자열 길이-1 만큼 반복문을 돌며 각 자리수만큼 자른다 ex) 두개씩 자를 때 aa / bb / ac / cc / cc

2. 딕셔너리에 저장하여 중복을 체크한다. ex ) aa: 1, bb: 1, ac: 1, cc:2

3. 각 자리수로 자른 것들의 최종 문자 개수를 센다

4. 가장 작은 값을 반환한다.

from collections import Counter

def solution(s):
    answer = 0
    results = [0 for i in range(len(s) - 1)]
    
    for i in range(1, len(s)):
        dic = {}
        for j in range(0, len(s), i):
            if j + i > len(s):
                break
            if s[j:j+i] in dic:
                dic[s[j:j+i]] += 1
            else:
                dic[s[j:j+i]] = 1
        for v in dic.values():
            if v == 1:
                results[i-1] += i
            else:
                results[i-1] += i+1
        print(dic)

    print(results)    
    
    return answer

라고 생각하고 짰는데.. 생각해보니 앞-뒤에 연결된 것만 중복으로 치고  aabcaa 에서 앞 aa와 뒤 aa는 압축이 안 된다는 것을 고려 안했다.

순서를 반영하지 않는 딕셔너리에서 자른 문자열과 압축 횟수를 저장하는 튜플의 리스트로 변경해서 다시 짰다.

근데 튜플은 값 변경이 되지 않는다 해서 다시 이중배열로 짬..

from collections import Counter

def solution(s):
    results = [0 for i in range(len(s) - 1)]
    
    for i in range(1, len(s)):
        arr = []
        k = 0
        for j in range(0, len(s), i):
            if j + i > len(s):
                results[i-1] += len(s)-j
                break
            
            if j == 0 or arr[k-1][0] != s[j:j+i]:
                arr.append([s[j:j+i], 1])
                k += 1
            else:
                arr[k-1][1] += 1
        
        for a in arr:
            if a[1] == 1:
                results[i-1] += i
            else:
                results[i-1] += (i+1)
                
    return min(results)

출력예시

결과

예외가 있나보다 ㅜ

"aaaaaaaaaa"처럼 중복이 10번 이상 되는 문자열의 경우에서 내가 자릿수를 1로 처리해버려서 발생하는 오류였다.

마지막 반복문에서 

else:
	results[i-1] += i + len(str(a[1]))

로 바꿔주면서 오류는 해결됐다.

테스트케이스 5번 런타임 에러는 문자열의 길이가 1일때 발생하는 배열 인덱스 오류였던 같다.

최종 코드

def solution(s):
    results = [0 for i in range(len(s)//2)]
    
    if len(s) == 1:
        return 1
    
    for i in range(1, len(s)//2 + 1):
        arr = []
        k = 0
        for j in range(0, len(s), i):
            if j + i > len(s):
                results[i-1] += len(s)-j
                break
            
            if j == 0 or arr[k-1][0] != s[j:j+i]:
                arr.append([s[j:j+i], 1])
                k += 1
            else:
                arr[k-1][1] += 1
        
        for a in arr:
            if a[1] == 1:
                results[i-1] += i
            else:
                results[i-1] += i + len(str(a[1]))
        
        
    return min(results)

 

---

다른 사람의 풀이

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

로직 자체는 크게 다를 것 없어 보이는데 코드가 많이 다르다

파이썬은 언제쯤 익숙해질까 흑흑