반란군의 음모 (Conspiracy)

문제

인덱스국 전쟁사 : Day 1

인덱스국은 매우 강력한 중앙 집권 국가입니다. 하지만 국왕 (검열됨)이 모든 국민에게 인덱 스 트리 사용을 의무화 하는 실정을 저질러 민심은 땅에 떨어져 있습니다. 당장 반란이 일어나도 이상하지 않은 시국이었지만, 인덱스국의 용맹한 장수이자 천재 조교인 앤디의 위용 탓에 쉽사리 반란이 일어나지 않았습니다.

그러던 어느 날, 성내에 위장 취업한 반란군의 첩자 뚜벤은 인덱스 트리를 정리하던 도중 흥미로운 사실을 발견하게 됩니다. (검열됨)의 인덱스 트리는 0-based이고, 앤디의 인덱스 트리 는 1-based였던 것입니다! 모름지기 0-based와 1-based는 철천지원수 지간인 것, 아니나 다를까 뚜벤이 (검열됨) 앞에서 "11!"이라고 외치자 (검열됨)은 발작을 일으켰고, 앤디 앞에서 "00..." 이라고 중얼거리자 앤디는 갑자기 욕설을 하며 자리를 떠나버렸습니다.

뚜벤은 (검열됨)과 앤디가 군사 기밀을 주고받을 때 이진 문자열을 이용한다는 사실을 알아 냈습니다. 그런데 과연, (검열됨)은 0-based답게 이웃한 1을 포함하는 문자열을 사용하지 않았고, 앤디는 1-based답게 이웃한 0을 포함하는 문자열을 사용하지 않았습니다!

뚜벤은 두 가지 이진 문자열을 대응시키는 방법을 추가로 알아냈는데, 문자열의 시작에 붙어 있는 0 (leading-0)들을 제거한 뒤 문자열을 정렬하는 것이었습니다. 문자열은 길이가 짧은 것이 우선순위가 높고, 같은 길이의 문자열이라면 사전 순으로 빠른 것이 우선순위가 높습니다. 동일 한 우선순위를 갖는 (검열됨)-문자열과 앤디-문자열이 쌍을 이루는데, 처음 몇 개의 문자열 변환 규칙은 아래와 같습니다.

번호	(검열됨)-문자열	앤디-문자열
0	0	0
1	1	1
2	10	10
3	100	11
4	101	101
5	1000	110
6	1001	111
7	1010	1010
8	10000	1011
9	10001	1101
10	10010	1110

뚜벤에게서 정보를 받은 반란군은 (검열됨)과 앤디 사이의 군 연락망을 교란시키고자 합니다.

이를 위해서는 (검열됨)-문자열과 앤디-문자열의 변환 규칙부터 파악해야 합니다. 어떤 (검열됨)- 문자열이 주어졌을 때, 대응되는 앤디-문자열로 변환하는 프로그램을 작성해주세요.

구현 세부 사항

다음 함수를 구현하세요.

string convert(string C)

• 이 함수는 처음 단 한 번 그레이더에 의해 호출됩니다.

• C는 길이 N의 (검열됨)-문자열입니다.

• C는 올바른 (검열됨)-문자열임이 보장됩니다. 즉, C = "0"을 제외하고는 첫 문자가 '0'이 아니며, "11"을 포함하지 않습니다.

• 이 함수는 C에 대응되는 올바른 앤디-문자열을 반환해야 합니다.

제한 조건

• 1 ≤ N ≤ 5,000,000

서브태스크

서브태스크	점수	N
1	4	N ≤ 20
2	5	N ≤ 80
3	6	N ≤ 5,000
4	5	N ≤ 5,000,000

예제 입출력

C = "10010"

그레이더는 다음 함수를 호출합니다.

convert(10010) = 1110

샘플 그레이더

Sample Grader는 다음과 같은 형식으로 입력을 받습니다.

• line 1 : C