[day20] 코딩테스트 알고리즘 - 문자열 압축 (feat.파이썬)

프로그래머스

💚 문제 포인트

1. 문자열 압축

2. 문자를 2개단위, 3개단위..4개단위로 쪼갠다

3. 같은 값이 연속해서 나타나는 지 체크

4. 값들 중 최소값을 구하라

아래에서 좀 더 자세히 설명해보겠다.

 

💚 문제 포인트 설명 

1. 문자열 압축  `str +=` 방식으로 문자열을 줄여나간다.

str = 'aaa'
str += 1 + 'hihih'

# 'aaa1hihih'

2. 문자를 n개 단위로 쪼갠다. for문을 중첩으로 돌며 단위로 쪼개준다. 

for i in range(1, len(s)):
	for j in range(i, len(s), i):
    	s[j:j+i]
        #a, a, b, b, a, c ..
        #aa, bb, ac ..
        #aab, bba, ccc ..

3. 같은 값이 연속해서 나타나는지 체크.

for (생략) :
	if temp = s[j:j+i]: #따끈따끈한 s[j:j+i]와 이전의 낡은 s[j:j+i]를 비교
		#(생략)
    else:
    	#(생략)
    temp = s[j:j+i] #다음 순서에서 비교해야하는 값을 저장해줌

4. 값들 중 최소값을 구하라

answer = 10000
for ..(생략) :
	#(생략)
    result = #'(생략)'
	answer = min(answer, len(result))
    
# 위와같이 하면 for문의 결과값 중 최솟값을 구할 수 있다.
# answer = 10000
# answer = 8
	...
# answer = 7

 

💚 참고 코드

def solution(s):
  answer = 10000
  for i in range(1, len(s)//2 + 1):
    result = ""
    count = 1
    temp = s[:i]
    for j in range(i, len(s) + i, i):
      #print('temp', temp,'s[j:j+i]',  s[j:j+i])
      if temp == s[j:j+i]:
        #print('same')
        count += 1
      else: #temp와 s[j:j+i]가 다를때 문자열을 압축해줌.
        #print('diff')
        if count == 1:
          result += temp
        else:
          result += str(count) + temp
        #print('result', result)
        #print('---------------------------')
        temp = s[j:j+i]
        count = 1
    answer = min(answer, len(result))
  return answer
print(solution('aabbaccc'))


# temp a s[j:j+i] a
# same
# temp a s[j:j+i] b
# diff
# result 2a
# ---------------------------

# temp b s[j:j+i] b
# same
# temp b s[j:j+i] a
# diff
# result 2a2b
# ---------------------------

# temp a s[j:j+i] c
# diff
# result 2a2ba
# ---------------------------

# temp c s[j:j+i] c
# same
# temp c s[j:j+i] c
# same
# temp c s[j:j+i] 
# diff
# result 2a2ba3c
# ---------------------------


# temp aa s[j:j+i] bb
# diff
# result aa
# ---------------------------

# temp bb s[j:j+i] ac
# diff
# result aabb
# ---------------------------

# temp ac s[j:j+i] cc
# diff
# result aabbac
# ---------------------------

# temp cc s[j:j+i] 
# diff
# result aabbaccc
# ---------------------------


# temp aab s[j:j+i] bac
# diff
# result aab
# ---------------------------

# temp bac s[j:j+i] cc
# diff
# result aabbac
# ---------------------------

# temp cc s[j:j+i] 
# diff
# result aabbaccc
# ---------------------------


# temp aabb s[j:j+i] accc
# diff
# result aabb
# ---------------------------

# temp accc s[j:j+i] 
# diff
# result aabbaccc
# ---------------------------