[BOJ 20310] 타노스

문자열 $S$에서 0과 1을 각각 절반씩 제거하여 새로운 문자열 $S'$을 만들었을 때, 그중 사전순으로 가장 빠른 것을 구해야 한다. 

 

사전순으로 앞에 나오기 위해서는 0이 1보다 앞에 나오는 것이 이득이다. 즉, 앞에서부터 읽어보며 0이면 출력하고 1이면 제거하는 것을 각 숫자 개수의 절반씩 진행하면 된다. 0은 그 이후로는 제거하고, 1은 출력하면 사전순으로 가장 빠른 것을 구할 수 있다.

 

string s, ans;
int cnt[2];

int main(void) {
    fastio;
    cin >> s;
    for (char c : s) cnt[c - '0']++;
    cnt[0] /= 2, cnt[1] /= 2;

    for (char c : s) {
        if (c == '0' && cnt[0]) cnt[0]--, ans += c;
        else if (c == '1') {
            if (cnt[1]) cnt[1]--;
            else ans += c;
        }
    }
    cout << ans;
    return 0;
}