[이코테] 구현 - 문자열 압축 python

난이도 : ●◐○ | 풀이 시간 : 30분 | 시간 제한 : 1초 | 메모리 제한 : 128MB | 기출 : 2020 카카오 신입 공채

 

문제

• 어피치는 문자열을 압축하는 방법에 대해 공부하고 있다.
• 그 방법은 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 것이다.
• 어피치는 문자열을 1개 이상의 단위로 잘라 압축해 보다 짧은 문자열로 표현할 수 있는 방법을 찾아보려고 한다.
• 예를 들어 "abcabcdede"인 경우 문자를 2개 단위로 잘라 압축하면 "abcabc2de"가 되지만 3개 단위로 잘라 압축하면 "2abcdede"가 되어 더 짧은 압축 방법이 된다.
• 압축할 문자열 s가 매개변수로 주어질 때 1개 이상의 단위로 문자열을 잘라 압축해 표현한 문자열 중 가장 짧은 것의 길이를 return하도록 solution 함수를 완성하라.
• 이 문제는 기본 코드가 제공되기 때문에 아래 링크에서 풀어야 한다.
• https://school.programmers.co.kr/learn/courses/30/lessons/60057

프로그래머스

 

 

제한 사항

• 1<=s의 길이<=1,000
• s는 알파벳 소문자로만 이루어져 있다.

 

입력예시

abcabcdede

출력예시

8

 

아이디어

• 문자열 s를 입력받는다.
• 압축을 했을 때 나올 수 있는 최장길이인 len(s)로 result라는 변수를 초기화한다.
• 압축하는 단위를 size라고 하고 1부터 len(s)//2까지 1씩 증가시키며 아래 과정을 반복한다.
  • 빈 문자열 tmp를 만들고, 연속된 같은 문자열의 수를 세는 변수 cnt =1을 만든다.
  • s를 size만큼씩 슬라이싱해서 prev라는 변수에 저장한다.
  • 연속해서 prev와 같은 게 나오면 cnt를 1 증가시킨다.
  • 다른 문자열이 나왔다면
    • cnt가 1인 경우
      • 압축할 수 없는 것이므로 prev를 tmp에 그대로 추가한다.
    • cnt가 2 이상인 경우
      • str(cnt)와 prev를 tmp에 추가한다.
      • prev를 갱신한다.
  • 마지막에 남은 문자열 조각도 tmp에 추가해줘야 한다.
    • cnt가 1인 경우
      • 압축할 수 없는 것이므로 prev를 tmp에 그대로 추가한다.
    • cnt가 2 이상인 경우 
      
      • str(cnt)와 prev를 tmp에 추가한다.
      • prev를 갱신한다.
  • tmp가 다 완성됐다면 result = min(result, len(tmp))로 압축된 문자열의 길이를 비교한다.

 

코드

def solution(s):
    answer = len(s)
    for size in range(1,len(s)//2+1):
        tmp = ""
        cnt = 1
        prev = s[0:size]
        for i in range(size,len(s),size):
            if prev==s[i:i+size]:
                cnt +=1
            else:
                tmp += str(cnt) + prev if cnt>=2 else prev
                prev = s[i:i+size]
                cnt = 1
        tmp += str(cnt)+prev if cnt>=2 else prev
        answer = min(answer, len(tmp))
    return answer