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

1. 문제

출처 : 프로그래머스

2. 소스코드 (Python3)

def solution(s):     # wordlen=len(s)이면 압축문자열 길이 = len(s)     answer = len(s)         for wordlen in range(1, len(s)-1):  #문자길이가 1~len(s)-1까지 반복.         wordcnt = len(s)//wordlen   #문자뭉텅이 개수 = 전체문자열길이에서 문자길이 나눈 몫         comp = False    #False=압축x, True=압축o         compcnt = 0     #압축되는 문자뭉텅이 개수         compstr = ''    #압축된 문자열         ## j번째 문자뭉텅이 처리         for j in range(wordcnt):              word1 = s[j*wordlen: (j+1)*wordlen]             word2 = s[(j+1)*wordlen: (j+2)*wordlen]             if j==wordcnt-1: word2 = s[(j+1)*wordlen:] #마지만 뭉텅이 예외처리             if word1 == word2:  #앞 문자와 뒤 문자가 같으면                 if not comp: comp, compcnt = True, 1    #압축x였던 경우: 압축설정                 compcnt += 1    #압축되는 문자개수 +1             else:                 if comp:                     compstr += str(compcnt)    #압축o인 경우: 앞에 압축되는 문자 개수 써주기                     comp, compcnt = False, 0    #압축설정 해제                 compstr += word1    #문자열 더함         ##마지막 문자 뭉텅이 처리         if comp: compstr += str(compcnt)    #압축o인 경우: 앞에 압축되는 문자 개수 써주기         compstr += word2    #문자열 더함         ##문자열 길이 중 최소인 것 answer에 담기         if answer > len(compstr):             answer = len(compstr)               return answer

 

3. 고찰

1) 변수 소개

문자열 s에 대해서 1~s의 길이만큼 나누어 압축한다. 주의할 점은 문자열이 꼭 같은 개수로 나누어질 필요가 없다는 점이다. 마지막 남은 문자들을 하나의 뭉텅이로 처리한다.

wordlen : 문자뭉텅이의 길이 (ex. 3)

wordcnt : 문자뭉텅이의 개수 (ex. 4)

comp      : 압축되는지 여부. 압축되면 True, 안되면 False. default=False

compcnt  : 압축되는 문자뭉텅이 개수

compstr   : 압축된 문자열

 

2) 알고리즘

문자열의 길이만큼의 길이로 압축하면 압축문자열은 문자열 그대로이다. 이때 압축문자열길이 = 문자열길이 이다.

첫 answer에 문자열길이를 저장한다.

문자뭉텅이 길이가 1 ~ len(s)-1까지 반복한다. len(s)인 경우는 위에서 처리함.

문자뭉텅이 개수(wordcnt)는 전체 문자열 길이 ÷ 문자뭉텅이 길이의 몫이다.

초기 압축 설정을 해준다.

## j번째 문자뭉텅이 처리

for문을 돌면서 각 문자뭉텅이에 대해서 다음 문자뭉텅이와 같은지 비교한다.

    word1은 앞의 문자뭉텅이. wordlen길이의 문자열

    word2는 이어지는 뒤의 문자 뭉텅이. wordlen길이의 문자열

    word2의 경우, 맨 마지막 뭉텅이면 길이가 다르기 때문에 예외처리하였다.

    앞 문자뭉텅이와 뒤 문자뭉텅이가 같으면 압축설정

        이전까지 압축x였던 경우는 새로 압축설정을 해준다.

        압축되는 문자개수 +1

    앞 문자뭉텅이와 뒤 문자뭉텅이가 다른 경우 압축해제 및 문자열 더하기

        이전까지 압축o였던 경우는 압축설정을 해제한다.

        문자열을 더해준다.

## 마지막 문자뭉텅이 처리

위와 같이 처리함.

최종적으로 압축문자열 길이를 계산하여 최소인 것을 answer에 저장한다.

 

3) 시간복잡도

입력 문자열의 길이를 N이라 할 때,

압축문자열길이가 1~N인 경우를 모두 조사한다. (N번 수행)

    그 안에서 각 문자뭉텅이 개수만큼 for문을 돌린다.

    문자 뭉텅이 개수는 매번 다르지만, 1~N까지 있으므로 평균 N/2라고 잡을 수 있을 것 같다. (N/2번 수행)

따라서 이 코드의 시간복잡도는 O(N*N/2) = O(N^2)이다.