[프로그래머스] 문자열 압축

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

프로그래머스

---

풀이 참고 --> 이것이 취업을 위한 코딩테스트다 (나동빈)

 

이건 내가 풀었다기보다,, 풀다가 실패하고 책보면서 공부하고, 간단하게 정리한 글이다.

---

입력으로 주어지는 문자열 길이가 1000 이하이므로,

완전탐색으로 가능한 모든 경우의 수를 탐색해보면 되는 문제이다!

 

따라서 문자열을 1개, 2개, 3개, 4개, ... , len(s)//2 개 까지 잘라서 압축된 문자열 길이를 비교해보고,

이 중 가장 짧은 것을 리턴해주면 된다.

 

 

인덱스 똑바로 세면서 문자열 슬라이싱 잘 하면 된다.

정답 코드 보고 이해하는 건 정말 쉽다. 근데 이제 이게 혼자 서 구현하려니까 어려웠던..문제다..

아직은 연습이 훨씬 많이 필요한 것 같다.

---

이코테 책에 나온 정답 코드

def solution(s):
  answer = len(s)
  for n in range(1, len(s)//2+1): #문자열을 n개단위로 잘라서 압축해본다
    compressed=""
    prev = s[:n] #맨앞부터 step까지 문자열 추출
    cnt = 1 
    #n부터 n씩 증가시키며 문자열 추출
    for i in range(n, len(s), n):
      if prev == s[i:i+n]: #이전 문자열과 동일하다면 cnt를 증가
        cnt += 1
    else: #아니라면 적절히 문자열에 추가해준 후 cnt를 초기화
      compressed += str(cnt) + prev if cnt>=2 else prev
      prev = s[i:i+n]
      cnt += 1
    #남아있는 문자열 처리  
    compressed += str(cnt) + prev if cnt>=2 else prev 
    answer = min(answer, len(compressed))
  return answer

 

 

---

내 풀이 (2023.03.26)

 

my_str = "aabbaccc"

# 압축단위: 1부터 문자열 길이의 절반까지
token = 1
ans = int(1e9)
while token <= len(my_str)//2:
  temp = ''
  arr = [] #문자열을 잘라서 저장
  i = 0
  while i < len(my_str):
    arr.append(my_str[i:i+token])
    i += token
    
  before = ''
  cnt = 1
  for x in arr:
    if x == before: # 앞의 문자와 같으면 카운트 증가시키기
      cnt += 1
    else: # 아니라면 문자열에 추가해주고 카운트, 앞의문자 값 바꿔주기
      if cnt > 1:
         temp += str(cnt) + before
         cnt = 1
      else:
         temp += before
      before = x
  # 마지막 남은 문자열 처리    
  if cnt>1:
    temp += str(cnt) + before
  else:
    temp += before
  
  token += 1
  ans = min(ans, len(temp))

print(ans)

추출한 문자열을 배열에 저장해두고, 배열을 또다시 순회할 필요 없이 바로바로 해주면 되는구낭..!