타노스

면접 대비

시간 제한1초메모리 제한1024 MB

요약

0과 1의 개수가 각각 짝수인 이진 문자열에서 두 숫자를 각각 절반씩 남겨 사전순으로 가장 작은 부분 수열을 구합니다.

문제

어느 날 타노스는 0과 1로 이루어진 문자열 $S$ 를 보았다. 신기하게도 $S$ 에 포함된 0의 개수와 1의 개수는 모두 짝수이다.

심술이 난 타노스는 $S$ 를 구성하는 문자 중 0의 절반과 1의 절반을 지워 새로운 문자열 $S'$ 를 만들려고 한다. $S'$ 가 될 수 있는 문자열 중 사전순으로 가장 앞서는 것을 구하시오.

문자열 $S$ 가 주어진다.

$S'$ 가 될 수 있는 문자열 중 사전순으로 가장 앞서는 것을 출력한다.

$S$ 의 길이는 $2$ 이상 $500$ 이하이다.

$S$ 는 짝수 개의 0과 짝수 개의 1로 이루어져 있다.