[카카오] 2020 KAKAO BLIND RECRUITMENT 1차 풀이 – 문자열 압축

Posted on by

이 포스팅에서는 2020 카카오 블라인드 채용 1차 문제인 ‘문자열 압축’ 문제를 해설합니다. 본 풀이에 대한 테스트는 https://programmers.co.kr/learn/courses/30/lessons/60057에서 수행하였으며 공식 풀이와 일치하지 않을 수 있습니다.

공식 풀이는 링크를 참조하시기 바랍니다.

문자열 압축

출처 : 2020 KAKAO 블라인드 채용 온라인 1차
링크 : https://programmers.co.kr/learn/courses/30/lessons/60057
카테고리 : Backtracking
난이도 : 쉬움

문제 요약

문자열이 주어질 때 임의의 단위 N으로 압축하여 만들어지는 최소 길이 문자열의 길이를 리턴하여라. 압축 단위 N은 1 ~ 문자열의 길이가 가능하다.

예를 들어 abcabcddab를 길이 3으로 압축하면 abc abc dda b에서 abc가 2개, dda는 하나 그리고 b가 하나이므로 2abcddab로 길이는 8이 된다.

문제 풀이

  • 초기의 정답은 압축하지 않은 상태의 길이인 len(text)로 둔다.
  • 압축 단위가 len(text)의 절반보다 클 때는 압축한 결과가 무조건 원래 길이보다 크기 때문에 수행할 필요가 없다. 따라서 [1, len(text) // 2] 구간의 압축 단위에 대해서만 압축을 수행한다.
  • 가능한 압축 단위에 대해 아래를 반복한다.
    • 누적 길이를 0으로 초기화한다.
    • 초기 인덱스 idx = 0으로 설정하고, idx < len(text)인 조건에서 아래를 반복한다
      • text의 idx 위치에서 압축 단위만큼 문자열을 자른다. 만약 남은 길이가 모자라면 모자란 만큼만 잘라 token에 저장한다.
      • token이 text에서 몇 번이나 반복되는지 센다.
      • token의 길이를 누적 길이에 더한다.
      • 반복 횟수가 1보다 크면 압축할 필요가 있으므로 반복 횟수의 길이도 누적 길이에 더한다.
    • 누적 길이가 현재 정답보다 작은 값이면 현재 정답을 갱신한다.
  • 정답을 리턴한다.

정답 코드

def solution(s):
    min_len = len(s)
    for i in range(1, len(s) // 2 + 1):
        length = 0
        prev = “”
        idx = 0
        while idx < len(s):
            token = s[idx:min(idx+i, len(s))]
            idx += len(token)
            cnt = 1
            length += len(token)
            while idx + i <= len(s) and token == s[idx:idx + i]:
                idx += i
                cnt += 1
            if cnt > 1:
                length += len(str(cnt))
        if length < min_len:
            min_len = length
    return min_len
cs

Competition 카카오 블라인드 채용 문자열 압축