가역 압축

데이터 압축은 정보 사회에서 필수적인 기술이다. 압축은 주어진 문자열을 (가능하면) 더 짧은 부호 문자열로 바꾸어 저장하거나 전송을 효율적으로 하게 한다.

부호 문자열을 뒤집어도 원래 문자열로 복호할 수 있는 새로운 압축 알고리즘을 설계하려고 한다. 현재 검토 중인 후보 명세는 다음과 같다.

• 주어진 문자열은 십진수 숫자의 열이다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9이다.
• 부호 문자열은 부호 단어의 열이다. 부호 단어는 십진수 두 자리 A와 L로 이루어진다. 따라서 부호 문자열은 짝수 개의 십진수 자리로 이루어진 열이다.
• 부호 문자열 A$1$L$1$ $\cdots$ A$k$L$k$는 아래 절차로 문자열에 복호된다. 편의상 십진수 자리(A$i$ 또는 L$i$)는 그 자리가 나타내는 한 자리 정수로도 취급한다.

i <- 1
while i <= k:
    if A_i가 0이면: L_i를 출력
    else if L_i가 0이면: 아무 것도 하지 않음
    else if A_i가 지금까지 출력된 자리 수보다 크면: 오류 발생
    else: L_i번 반복하여, 지금까지 출력된 자리 중 뒤에서 A_i번째 자리를 출력
    i <- i + 1

예를 들어 부호 문자열 000125는 다음과 같이 0101010으로 복호된다.

1. 첫 부호 단어 00은 0을 출력한다.
2. 둘째 부호 단어 01은 1을 출력한다.
3. 마지막 부호 단어 25의 첫 자리 2는 지금까지 복호된 자리를 뒤에서 셀 때 두 번째 자리를 출력하라는 뜻이다. 이를 다섯 번 반복한다. 첫 번째 반복에서 지금까지 복호된 자리는 0, 1이므로 뒤에서 두 번째인 0을 출력한다. 두 번째 반복에서는 0, 1, 0이므로 뒤에서 두 번째인 1을 출력한다. 나머지 세 번은 차례로 0, 1, 0을 출력한다.

오류 없이 끝나는 부호 단어의 열을 유효한 부호 문자열이라고 한다. 유효한 부호 문자열을 뒤집은 것도 유효하고, 원래 문자열과 뒤집은 문자열이 같은 문자열로 복호될 때, 그 부호 문자열은 가역적이다.

예를 들어 000125는 뒤집은 521000이 오류를 일으키므로 유효하지 않고, 따라서 가역적이지 않다. 0010은 뒤집은 0100이 유효하지만, 0010은 0으로, 0100은 10으로 복호되므로 가역적이지 않다. 반면 0015599100은 자신과 뒤집은 0019955100이 모두 00000000000000000으로 복호되므로 가역적이다.

이 압축 방식의 성능을 다양한 경우에서 평가하려고 한다. 임의의 숫자 문자열이 주어졌을 때, 그 문자열로 복호되는 가역적 부호 문자열 가운데 가장 짧은 것을 찾는 프로그램을 작성하라.

십진수 숫자로 이루어진 비어 있지 않은 문자열 $s$가 한 줄에 주어진다. $s$의 길이는 500을 넘지 않는다.

$s$로 복호되는 가장 짧은 가역적 부호 문자열을 출력한다. 가장 짧은 해가 여럿이면 사전순으로 가장 앞선 것을 출력한다. 입력 문자열이 무엇이든 가역적 부호 문자열은 항상 존재한다.