사용자 도구

사이트 도구


ps:problems:programmers:60057

문자열 압축

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호60057
문제명문자열 압축
레벨Level 2
분류

기초

시간복잡도O(nlogn)
인풋사이즈n<=1000
사용한 언어Python
해결날짜2021/07/30

풀이

  • 그냥 무식하게, 문자를 1개단위, 2개단위, …, |s|개 단위로 모두 압축해보고, 그중에서 가장 길이가 짧은것을 찾으면 된다.
    • 단위가 전체 길이의 절반을 넘어가면 압축이 불가능하므로, |s|/2 까지만 해봐도 되긴 하다만, 큰 의미는 없다.
  • i개 단위로 압축을 해볼때 걸리는 시간은, i값에 관계 없이 O(log|s|) 이다. 따라서 전체 시간 복잡도는 O(|s|*log|s|).
  • 실수하기 쉬운 부분은, i개 단위로 압축할 때 i길이의 문자열이 x번 반복된다면 압축된 길이는 i+1 이 아니라, i + len(str(x))이다. x가 1자리수보다 클 경우도 생각해야 한다는 의미이다.

코드

"""Solution code for "Programmers 60057. 문자열 압축".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/60057
- Solution link: http://www.teferi.net/ps/problems/programmers/60057
"""

import itertools


def chars(group, size):
    count = sum(1 for _ in group)
    if count > 1:
        return size + len(str(count))
    else:
        return size


def solution(s):
    answer = len(s)
    for size in range(1, len(s)):
        pieces = (s[pos:pos + size] for pos in range(0, len(s), size))
        length = sum(chars(g, len(k)) for k, g in itertools.groupby(pieces))
        answer = min(answer, length)
    return answer

토론

댓글을 입력하세요:
Y B G T X
 
ps/problems/programmers/60057.txt · 마지막으로 수정됨: 2021/07/31 16:51 저자 teferi