koosaga   9달 전

RLE(Run Length Encdoing) 방법은 이러한 압축 방법 중 가장 기초적인 방법이다. RLE는 문자열에서 어떤 문자가 반복될 경우, 이 문자를 한 번만 저장하고 그 대신 반복 회수를 저장하는 방법이다. 이를 이용하면 abccddd는 abc2d3와 같이 압축될 수 있다.


문자 대신 문자열을 이용하면 RLE를 좀 더 개선할 수 있다. 예를 들어 주어진 문자열에서 S라는 문자열이 k번 반복될 경우, 이를 k(S)와 같은 식으로 표현할 수 있다. 예를 들어 letsgogogo는 lets3(go)와 같이 압축될 수 있다. 이 경우 원래 문자열의 길이는 10이지만 압축된 문자열의 길이는
9가 된다. 압축된 문자열의 길이를 계산할 때에는 괄호와 k를 나타낼 때 필요한 길이도 포함해서 계산한다. 또, 압축을 중첩해서 할 수도 있는데, 예를 들어 nowletsgogogoletsgogogo는 now2(lets3(go))로, nowletsgogogoletsgogogoandrunrunrun 은 now2(lets3(go))and3(run)으로 압축될 수 있다.


개선된 RLE에서 abc2d3와 같은 압축 방법은 금지됩니다. 고로, ab2(c)3(d)와 같이"만" 압축해야 하고 이 점을 고려치 않으면 틀립니다. 반영해주세요.

baekjoon   9달 전

수정했습니다.

댓글을 작성하려면 로그인해야 합니다.