[백준(BOJ)] 타노스(20310번)_C++

어떻게 해야 사전순으로 가장 빠른 문자열을 만들 수 있을까?

'0'과 '1' 중 사전순으로 더 빠른 것은 '0'이다.

"10"과 "01" 중 사전순으로 더 빠른 것은 "01"이다.

즉, 사전순으로 더 빠른 문자가 앞쪽에 올수록 사전순으로 빠른 문자열이 된다.

 

우리는 '0'이 최대한 앞에 나오고, '1'이 최대한 뒤에 나오는 문자열이 되도록 해야 한다.

그러면 '0'은 뒤에서 부터 없애고, '1'은 앞에서 부터 없애면 된다.

 

이를 구현하는 것은 그리 어렵지 않다.

 

---

정답 코드

#include <iostream>

using namespace std;

string s, answer;
int cnt0, cnt1;

int main(){
    cin.tie(NULL);
    cout.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> s;

    for (int i = 0; i < s.length(); i++){
        if (s[i] == '0')
            cnt0++;
        if (s[i] == '1')
            cnt1++;
    }
    cnt0 /= 2;
    cnt1 /= 2;

    int idx = s.length() - 1;
    while (1){
        if (cnt0 == 0 || idx < 0)
            break;
        if (cnt0 > 0 && s[idx] == '0'){
            s.erase(idx, 1);
            cnt0--;
        }
        idx--;
    }

    idx = 0;
    while (1){
        if (cnt1 == 0 || idx == s.length())
            break;
        if (cnt1 > 0 && s[idx] == '1'){
            s.erase(idx, 1);
            idx--;
            cnt1--;
        }
        idx++;
    }

    cout << s;
}