[Level 2 프로그래머스] 카카오 기출, 2020 KAKAO BLIND RECRUITMENT - 문자열 압축(Python)

 

programmers.co.kr/learn/courses/30/lessons/60057

코딩테스트 연습 - 문자열 압축

 

문제 제목에 나와있듯이 문자열을 파싱하는 문제이다. 

 

문자열의 최대 길이가 1000이므로 완전탐색으로 해도 충분했다.

 

 

문제 해결

• 문자열의 길이가 n이라고 한다면, 문자열을 1부터 n/2개 까지 나눈다
• 나눈 문자열을 리스트에 넣는다,
  • 리스트에 들어간 n개씩 자른 문자열을 앞뒤로 비교해가며 같다면 1씩 늘린다.
  • 비교 과정에서 문자열이 다르다면 반복횟수와 반복문자열을 붙인다
  • 이때, 문자가 반복되지 않아 한번만 나타나는 경우에는 문자 앞에 1을 붙이는 것을 생략한다.
• 압축된 문자열의 길이들을 비교하여 가장 짧은 것을 리턴한다.

 

 

소스코드

  def cal(arr):
      result = ''
      num = 1
      #print("in func : ", arr)
      for i in range(len(arr)-1):
          if arr[i] == arr[i+1]:
              num+=1 
          else:
              if num == 1: result += arr[i]
              else: result += str(num)+arr[i]
              num = 1
      if num == 1: result += arr[len(arr)-1]
      else: result += str(num)+arr[len(arr)-1]
      return result

  def solution(s):
      answer = len(s) # 압축을 아예 못하는 경우    
      # 길이가 정해짐 1...n/2 까지 탐색
      for length in range(1, (len(s)//2)+1):
          tmp = []
          for i in range(0, len(s), length):
              tmp.append(s[i:i+length])        
          res = cal(tmp)
          answer = min(len(res), answer)
          #print(res)
      return answer

채점 결과