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

1. 문제

2. 소스코드

def solution(s):     # len(s)개 단위로 잘라 압축하는 경우     answer = len(s)         # 1 ~ len(s)-1개 단위로 잘라 압축하는 경우     for l in range(1, len(s)-1):         # 첫번째 압축 문자열         comp = [1, s[:l]]         # 다음 문자열들에 대해서 처리         for i in range(1, len(s)//l + bool(len(s)%l)):             word = s[i*l:(i+1)*l]             # 앞 문자와 같으면 숫자 +1             if word == comp[-1]:                 comp[-2] += 1             # 앞 문자와 다르면 새로 추가             else:                 comp += [1, word]         # int -> string으로 변환, 1이면 삭제         for i in range(0, len(comp), 2):             comp[i] = str(comp[i])             if comp[i] == '1': comp[i] = ''         # 문자열리스트 -> 문자열로 합치기         comp = ''.join(comp)         # 최소 길이 찾기         if answer > len(comp):             answer = len(comp)                 return answer

 

3. 고찰

l개 단위로 잘라서 압축하는 경우에 대해 각각 압축 문자열을 구하였다. l은 1 ~ len(s)까지 될 수 있다.

 

# len(s)개 단위로 잘라 압축하는 경우

그런데, len(s)개로 잘라서 압축하는 경우, 압축문자열은 s 그 자체이므로 이때 압축문자열의 길이는 len(s)이다.

따라서 len(s)개로 자른 압축문자열의 길이를 미리 answer에 저장하고 나중에 비교하였다.

 

시간복잡도는 O(1)이다.

 

# 1 ~ len(s)-1개 단위로 잘라 압축하는 경우

l 개 단위로 잘라서 각 압축 문자열을 구한다.

압축문자열은 [개수, 문자열]을 반복하여 만들었다.

첫번째 문자열은 미리 압축 문자열에 저장하였다.

다음 문자열들을 인덱스 슬라이싱을 통해 받아왔다.

문자열은 0~l-1, l~2l-1, 2l~3l-1, 3l~4l-1, ··· 이렇게 나뉜다.

다음 문자열이 바로 이전 문자열과 같으면 개수만 +1하고,

                                             다르면 [개수, 문자열]을 새로 추가해준다.

개수는 int형이기 때문에 string형으로 바꿔주었고, 문제에서 문자열의 개수가 1개이면 따로 압축 문자열에 표기하지 않으므로 삭제했다.

join함수를 이용해서 문자열리스트를 문자열로 합쳐서 압축 문자열을 구하였다.

해당 압축문자열들 중 최소길이를 찾아서 리턴.

 

시간복잡도는,

l = 1 ~ len(s)-1까지 반복 -> N번 반복

압축문자열 처리를 위한 for문 -> 문자열 개수만큼 반복. 즉 N÷l 만큼 반복한다.

따라서 시간 복잡도는 O(N^2)이다.