1638: 압축의 원리에 대해 알아보자

대표적인 압축의 원리는 Run Length Coding과 허프만 코딩이 있다. 실제 압축 프로그램에서 많이 사용되는 것은 허프만 코딩이지만 이 문제에서는 Run Length Coding에 대해 알아보도록 하겠다.

- Run Length Coding

AAAAAAABBCCCDEEEEFFFFFFG라는 텍스트가 있을 때 이것을 각각 '문자 X 반복 횟수'로 표현하는 방법이다. 

위의 텍스트는 원래 24개의 문자를 가져 24바이트의 용량이지만 A7B2C3D1E4F6G1으로 표현이 가능하기 때문에 결과적으로 14바이트로 줄어들게 된다. 

따라서 압축에 성공한 것이다. 

하지만 이러한 방식에 문제점이 많기 때문에 '전치문자'라는 것을 사용하는데 반복되는 문자는 '전치문자 X 반복된 횟수 X 반복 문자'와 같은 방식의 규칙을 적용하여 사용한다.

이러한 방식으로 위 텍스트를 다시 표현해보면 *7A*2B*3CD*4E*6FG가 되고 반복되지 않는 문자의 경우 그대로 출력된다.

전치문자 규칙을 바탕으로 입력된 텍스트를 압축하여 보자.

[2021년 고운고 2학년 김O중 제작]

첫 번째 줄에 압축할 텍스트를 입력한다

첫 번째 줄에는 전치문자 X 반복된 횟수 X 반복 문자로 압축한 텍스트를 출력한다.

반복되지 않는 문자는 전치문자와 반복된 횟수를 쓰지 않는다.

AAAAAAABBCCCDEEEEFFFFFFG

*7A*2B*3CD*4E*6FG