[programmers] 프로그래머스 문자열 압축(Python)

(주)그렙

[programmers] 프로그래머스 문자열 압축

(Python)

(글쓴날 : 2020.06.17)

 

---

* programmers, 프로그래머스 문제 Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

프로그래머스 문자열 압축

---

1) 문제

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/60057

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

---

2) 풀이 과정

* 시간 복잡도 : O(n²)

 

주어진 문자열을 반복되는 문자의 개수에 따라 압축할 때, 압축한 문자열의 최소 길이를 구하는 문제입니다.

 

저의 경우, 투 포인터 알고리즘을 적용하였고, Python을 사용했습니다.

문자열의 길이를 2로 나눈 몫만큼 압축할 단어의 길이를 제한하였고, 투 포인터를 이용한 리스트 슬라이싱을 통해 반복되는 문자열들을 딕셔너리에 저장해 압축하였습니다.

그렇게 압축할 단어의 길이마다 최종적으로 압축된 문자열들의 길이를 비교하여 가장 짧은 압축된 문자열의 길이를 구해 문제를 해결했습니다.

---

3) 코드

 

* Python 코드

def solution(s):
    if len(s) == 1:
        return 1
    
    answer = ""
    for c in range(1, len(s) // 2 + 1):
        start = 0
        finish = c
        
        temp = ""
        compString = ""
        compWord = dict()
        
        while 1:
            if start > len(s) - 1:
                break
                
            if not len(temp):
                temp = s[start:finish]
                compWord[temp] = 1
            else:
                if temp == s[start:finish]:
                    compWord[temp] = compWord[temp] + 1
                else:
                    compCount = compWord[temp]
                    if compCount > 1:
                        compString += str(compWord[temp])
                    compString += temp
                    
                    compWord = dict()
                    temp = s[start:finish]
                    compWord[temp] = 1
                    
            start += c
            finish += c
            
        compCount = compWord[temp]
        if compCount > 1:
            compString += str(compWord[temp])
        compString += temp
                    
        if not len(answer):
            answer = compString
        else:
            if len(answer) > len(compString):
                answer = compString
                
    return len(answer)

---