[구현] 문자열 압축

2020 카카오 신입 공채 문제다.

 

먼저 단순히 1개 단위로 자르면 어떻게 만들수 있을까 생각하면서 cutByOne 함수를 만들었다. 문자열 s 전체를 for문 돌면서 targetChar 를 이용해 resultS를 만들어갔다.

def cutByOne(s):
  resultS = ''
  count = 1
  targetChar = 'F'
  for i in range(len(s)):
    if targetChar == 'F':
      targetChar = s[i]
      count = 1
      continue

    if targetChar == s[i]:
      count += 1
    else:
      if count == 1:
        resultS += targetChar
        count = 1
        targetChar = s[i]
      else:
        resultS += str(count) + targetChar
        count = 1
        targetChar = s[i]

  # 마지막 남은거 처리
  if count == 1:
    resultS += targetChar
  else:
    resultS += str(count) + targetChar

  return len(resultS)

 

 

하지만 cutByOne 함수는 2개 이상으로 자를 때는 맞지 않는 코드였다. 2개 이상일때는 어떻게 처리할까 고민하다 입력받은 cutCount 에 맞게 list를 새로 만들었다. 예를들어 s가 ababcdcd 이고, cutCount 가 2이면 2개단위로 잘라서 새로운 리스트 ['ab', 'ab', 'cd', 'cd] 를 만들었다. 그리고 이미 만들어뒀던 cutByOne 함수를 활용했다. 

def getList(s, cutCount):
  list = []
  count = 0
  tempS = ''

  for i in range(len(s)):
    if count == cutCount:
      list.append(tempS)
      tempS = s[i]
      count = 1
    else:
      tempS += s[i]
      count += 1

  # 마지막 처리
  list.append(tempS)
  return list


def cutByParamCount(s, cutCount):
  list = getList(s, cutCount)
  return cutByOne(list)

 

 

이제 cutByParamCount 를 1개부터 입력받은 문자열 s 절반만큼 for 문 돌려서 가장 문자열수가 적은것을 출력하게 했다. s 절반까지로 한 이유는, 절반이 넘어가게 되면 비교가 불가능해지기 때문이다.

def solution(s):
    resultList = []
    answer = len(s)
    for i in range(len(s)//2):
        answer = min(answer, cutByParamCount(s, i+1))

    return answer

 

 

책의 정답 코드는 아래와 같다. 배열 [start:end] 문법을 이용했다. 그리고 두번째 for문에서 range(step, lens(s), step) 을 사용했다. 첫번째 for문에서  0 ~ step-1 만큼 뽑았으니, step 인덱스 부터 시작해서 step 단위로 for문을 돌겠다는 거다.

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

 

 

출처: 이것이 코딩 테스트다 나동빈 저