• 이코테책 516p
• 프로그래머스 문자열압축

문제

내 풀이

처음 든 생각

• 가장 큰 단위일때가 최적의 답이라고 생각했지만
  • 진짜 최적을 보장하는가..?
    • 8개 단위로 잘랐을때보다, 3개 단위로 잘랐을때가 더 짧게 나올수도 있나?
    • 아니다. 큰 단위로 자른다고해서 최적이 아님
    • 반례) aabbaabbccddeeff 일때
      4개 단위로 잘랐을때 : 2aabbccddeeff 13자리
      2개 단위로 잘랐을때 : 2a2b2c2d2e2f 12자리
• 그러면 반복되는 가장 긴 길이의 토큰을 찾아야 하나?
  • 이게 위에 적은 상황이라고 다르다고 생각했는데 같은 상황이었음
• 뭐 부터 찾는게 가장 빠른지,, 모르겠다.
  그냥 무식하게 구현(모든 토큰 길이마다 답을 기록해둿다가, 그 중 최솟값을 출력)해야하는 것 같다.
  • 주어지는 문자열 S는 최대 1000이니 괜찮을 것 같다.

풀이 아이디어

일단 무식하게 풀어보고
다 풀고나서 개선할 수 있으면 개선하자

풀면서 지나간 생각

중복 문자열 검색하는거 빠르게 하는 뭐 알고리즘 있었는데,, 하고 찾아보니까
2-2 알고리즘수업에서 문자열알고리즘을 배웠다

• naive하게 매칭 체크
• 오토마타를 이용하여 매칭 체크
• 라빈카프 알고리즘
• KMP 알고리즘
• 보이어무어 알고리즘

어,, 이걸 쓰게될까 ??

내 코드

# 토큰 길이가 주어졌을때의 중복문자열처리를 한 문자열의 길이를 리턴한다 
def check_zip(s, s_len, t_len) :
    cnt = 0
    for i in range(s_len-t_len*2) :
        if s[i:(i+t_len)] == s[(i+t_len):(i+t_len*2)] : #중복 발견
            cnt += 1
            i += t_len - 1 # 토큰길이만큼 건너뛰고 검색한다
    return s_len - cnt*t_len + cnt
    
    
    
def solution(s):
    min_len = 1001
    s_len = len(s)
    s_half_len = s_len //2 # 토큰길이에 있어 절반 이후는 검사할 필요가 없다. (어차피 길이가 줄어들지 않는다)
    
    for token_len in range(1, s_half_len) : # 모든 가능한 토큰 길이마다 계산해봄
        # 문자열 압축
        tmp_len = check_zip(s, s_len, token_len)
        
        if tmp_len < min_len : # 지금까지의 길이보다 더 적은 길이 발견
            min_len = tmp_len # 최솟값 갱신
        
    return min_len
    

다행히도 문자열알고리즘까지 쓸 일은 없었다 휴우우우우

책 코드

def solution(s) :
	answer = len(s)
	# 1개 단위 (step) 부터 압축 단위를 늘려가며 확인
	for step in range(1, len(s)//2 + 1) :
		compressed = ""
		prev = s[0:step] # 앞에서부터 step만큼의 문자열 추출
		count = 1
		# 단위(step) 크기만큼 증가시키며 이전 문자열과 비교
		for j in range(step, len(s), step) :
			#이전 상태와 동일하다면 압축횟수(count) 증가
			if prev == s[j:j+step] :
				count += 1
			# 다른 문자열이 나왔다면 (더이상 압축하지 못하는 경우라면)
			else :
				compressed += str(count) + prev if count >= 2 else prev
				prev = s[j:j+step] # 다시 상태 초기화
				count = 1
		# 남아있는 문자열에 대해 처리 
		compressed += str(count) + prev if count >= 2 else prev
		# 만들어지는 압축 문자열이 가장 짧은 것이 정답
		answer = min(answer, len(compressed))

	return answer