문자열 압축

https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

문제요약 :

앞에서 부터 n개씩나누어 같은숫자라면 aaa  > 3a 다음과 같이 축약해서 쓸수있다고 하면, 최소한의 압축은 몇번인가

 

소요시간:

30분 + 20분

 

1차 접근:

def solution(s):
	n = len(s)
	ans = [n]
	for i in range(1,n//2+1): #이 이상은 압축이 어차피 안됨
		temp =[0]
		for j in range(0,n,i): #i 씩 건너뛴다
			if j+2*i <= n and s[j:j+i] == s[j+i:j+2*i] : #연속으로 같다면 체크 
				temp[-1]+=1
			else:
				temp.append(0)
		ans.append(n-i*sum(temp) +len(''.join(map(str,temp)))-temp.count(0))
		#전체에서 중복된만큼 빼고 숫자가 그만큼 추가 됐으니까 추가하되, 0은 빼기
	return min(ans)

테케 2개 빼고 맞췄다. 15분동안 고민후 예외케이스를 못 찾아서 질문 확인해본 결과

n개가 겹치면  n 문자 로 표현해야 되는데 , 지금은 0부터 시작해서 n-1개 이기 때문에 10^n -1일때 오류가 났다.  

 

2차접근:

def solution(s):
	n = len(s)
	ans = [n]
	for i in range(1,n//2+1): #이 이상은 압축이 어차피 안됨
		temp =[0]
		for j in range(0,n,i): #i 씩 건너뛴다
			if j+2*i <= n and s[j:j+i] == s[j+i:j+2*i] : #연속으로 같다면 체크 
				temp[-1]+=1
			else:
				temp.append(0)
		ans.append(n-i*sum(temp) +len(''.join(map(str,[i+1 for i in temp])))-temp.count(0))
		#전체에서 중복된만큼 빼고 숫자가 그만큼 추가 됐으니까 추가하되, 0은 빼기
	return min(ans)

그래서 str에 들어가는 부분에 temp를 +=1을 해주었다.