[프로그래머스] 60057: 2020 KAKAO BLIND RECRUITMENT > 문자열 압축

안녕하세요.

이번 문제는 프로그래머스의 60057번 입니다.

문자열을 압축하는 문제입니다. 

 

문제

코드

def solution(s):
    result = set([len(s)])
    for i in range(1,len(s)):
        result.add(len(string_zip(s, i)))
        
    return min(result)
    
def string_zip(strs, n):
    result = ""
    target = strs[:n]
    count = 1
    
    for i in range(n, len(strs), n):
        if strs[i:i+n] == target:
            count += 1
        else:
            result += f"{count if count > 1 else ''}{target}"
            count = 1
            target = strs[i:i+n]
        
    result += f"{count if count > 1 else ''}{target}"
    
    return result

 

알고리즘 캔버스

아이디어

1. 기본적으로 압축하지 않은 결과를 set 형식인 result에 저장한다.
   1. 만약 len이 1일 경우를 대비해서 넣는다. result는 집합이기에 중복 값이 들어가도 상관 없음.
2. 1부터 s의 길이만큼 for문을 순회한다.
   1. string_zip 함수를 제작한다.
      1. 여기서 n은 zip할 문자열 길이를 말한다.
      2. 최초 비교 문자열을 n개의 개수만큼 자른다.
         1. 지금부터 이것은 target(비교 하려는 문자열) 이라고 부른다.
      3. n부터 s의 len 만큼, n을 step으로 해 range를 만든다.
      4. 그리고 그 range만큼 순회를 시작한다.
      5. 순회를 하며 현재 target과 바로 다음 오는 n개 만큼의 문자열을 비교한다.
         1. 같다면 연속되는 문자열이므로 count를 +1 시킨다.
         2. 같지 않다면 result에 target을 현재 쌓아온 count 와 함께 이어붙인다.
            1. 그리고 count를 1로 초기화한다.
            2. target을 다음 n 만큼의 문자열로 변경한다.
      6. 순회가 끝나면 남은 문자열을 count와 함께 이어붙이고 result를 반환한다.
   2. string_zip을 통해 나온 문자열의 len을 result set에 저장한다.
3. 최종적으로 가장 짧은 length를 result의 min 값으로 찾아 반환한다.

시간 복잡도 (Big-O)

- O(N^2)

 

테스트 케이스 

 

감사합니다.