백준 - 20310번 : 타노스 (C++)

풀이 방법 : 그리디

0의 절반만큼 0을 제거하고, 1의 절반만큼 1을 제거해서 사전순으로 가장 빠른 문자열을 구하는 문제다.

당연하게도 사전순으로 따지면 0이 1보다 앞에 온다. 그러므로 되도록이면 0이 앞에 있고 1이 뒤에 있는 문자열을 구하는게 맞을 것이다.

반복문을 돌려가며 0과 1 각각의 숫자를 세주고 각각 그 절반만큼 기존 문자열에서 제거를 해야하는데

인덱스를 증가시켜가면서 되도록 앞에 있는 1을 제거 시켜주고, 그 후에는 끝에서부터 인덱스를 감소 시켜가면서 0을 제거해주면 사전순으로 가장 먼저 등장하는 문자열이 등장할 것이다.

#include <iostream>
#include <string>

using namespace std;

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	string S;
	cin >> S;

	int Length = S.length();

	int ZeroCnt = 0;
	int OneCnt = 0;

	for (int i = 0; i < Length; ++i)
	{
		if (S[i] == '0')
		{
			++ZeroCnt;
		}

		else
		{
			++OneCnt;
		}
	}

	int CurOneCnt = 0;
	for (int i = 0; i < S.length(); ++i)
	{
		if (S[i] == '1')
		{
			S.erase(S.begin() + i);
			--i;
			++CurOneCnt;
		}

		if (CurOneCnt == OneCnt / 2)
			break;
	}

	int CurZeroCnt = 0;
	for (int i = S.length(); i >= 0; --i)
	{
		if (S[i] == '0')
		{
			S.erase(S.begin() + i);
			++i;
			++CurZeroCnt;
		}

		if (CurZeroCnt == ZeroCnt / 2)
			break;
	}

	cout << S;
}