상세 컨텐츠

본문 제목

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

Problem Solving/programmers

by HelloMinchan 2020. 6. 17. 04:41

본문

(주)그렙

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

(Python)

(글쓴날 : 2020.06.17)

 


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

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


 

 

프로그래머스 문자열 압축


1) 문제

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

 

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

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자

programmers.co.kr


2) 풀이 과정

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

 

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

 

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

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

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


3) 코드

 

* Python 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def solution(s):
    if len(s) == 1:
        return 1
    
    answer = ""
    for c in range(1len(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)

 

관련글 더보기

댓글 영역