백준 - 21314번 : 민겸 수 (C++)

풀이 방법 : 그리디

문제에 나온 규칙에 따라 이미 변환된 문자열을 다시 십진수로 변환하는 문제다. 변환할 때 나올 수 있는 숫자의 최댓값과 최솟값을 차례대로 출력해주면 된다.
입력으로 주어지는 문자열의 길이의 최댓값이 3000이므로 숫자 또한 문자열로 처리해주자.

최댓값 : M과 K를 무조건 묶어서 처리해줘야한다. 예를 들어 MK라고 할 때 따로 M -> 1, K -> 5 와 같이 변환하면 15가 되지만 묶어서 변환하면 50이다.

그리고 만약 K가 등장하지 않고 M만 연달아 등장하는 경우 따로 변환해줘야 한다. 예를 들어 MMMMM의 경우 한꺼번에 처리하면 10000이지만 따로 처리하면 11111이 된다.

최솟값 : 최댓값의 반대로 해주면 된다 K는 무조건 단일 5로 처리해주고 M이 연달아 등장하는 경우에는 무조건 한꺼번에 변환해준다.

#include <iostream>

using namespace std;

int main()
{
	string Num;
	cin >> Num;

	string Min = "";
	string Max = "";

	int Length = Num.length();

	string Temp = "";

	for (int i = Length - 1; i >= 0; --i)
	{
		if (Num[i] == 'K')
		{
			if (!Temp.empty())
			{
				if (Temp[0] != '5')
				{
					for (int j = 0; j < Temp.length(); ++j)
					{
						Temp[j] = '1';
					}
				}

				Max = Temp + Max;
				Temp = "";
			}


			Temp += '5';

		}

		else
		{
			if (Temp.empty())
				Temp += '1';

			else
				Temp += '0';

		}
	}

	if (Temp[0] != '5')
	{
		for (int i = 0; i < Temp.length(); ++i)
			Temp[i] = '1';
	}

	Max = Temp + Max;

	Temp = "";

	for (int i = Length - 1; i >= 0; --i)
	{

		if (Num[i] == 'K')
		{
			Min = '5' + Temp + Min;
			Temp = "";
		}

		else
		{
			if (Temp.empty())
				Temp += '1';

			else
				Temp += '0';
		}
	}

	Min = Temp + Min;

	cout << Max << '\n';
	cout << Min;
}