[C++] 백준 2870번: 수학숙제

문제 링크

https://www.acmicpc.net/problem/2870

풀이 방법

해당 문제를 푸는데 꽤 시간이 소모되었다. 이 문제를 해결하는데 가장 중요한 Key Points는 네 가지다.

• 우선 문자열 시작부터 탐색하여 숫자로만 이루어진 문자열을 추출한다.
• 추출한 해당 문자열이 모두 0으로 이루어져 있으면 "0"하나만 vector에 담는다
• 0으로 시작하는 숫자는 모두 무시하고 0 이후 시작되는 숫자부터 문자열을 다시 추출하여 vector에 담는다.
• 숫자를 int, long long 형으로 담으면 Over Flow가 발생할 수 있으니 문자열 그대로 비교 함수를 만들어서 숫자를 오름차순 정렬한다.

위 설명과 아래 코드의 주석을 참고해서 해당 문제를 이해하자!

코드

#include <bits/stdc++.h>
using namespace std;


bool chkZeroNum = false;

bool stringNumCmp(const string& s1, const string& s2) // 문자열로 구성된 숫자를 오름차순으로 만들기 위한 비교함수
{
	if (s1.size() != s2.size())
	{
		return s1.size() < s2.size();
	}

	return s1 < s2;
}

bool isAllZero(const string& s) // 모두 숫자 0으로 이루어진 문자열을 판별하는 함수
{
	bool chkAllZero = true;
	for (auto c : s)
	{
		if (c != '0')
		{
			chkAllZero = false;
			break;
		}
	}
	return chkAllZero;
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0);

	int n;
	string s;
	vector<string> result;

	cin >> n;

	while (n--)
	{
		cin >> s;
		int st = 0;
		int en = 0;
		for (int i = 0; i < s.size(); i++)
		{

			if ('0' <= s[i] && s[i] <= '9')
			{
				st = i;
				while ('0' <= s[i] && s[i] <= '9' && i < s.size())
				{
					i++;
				}
				en = i;
				string num = s.substr(st, en - st); // 숫자로만 이루어진 문자열을 탐색

				if (isAllZero(num))  // 추출한 문자열이 모두 숫자 0인 경우 EX) 0000,00,0
				{
					result.push_back("0");
					i--; // 추출한 문자열 다음 문자열 부터 다시 탐색
					continue;
				} // 추출한 숫자들로 이루어진 문자열 EX) 0020, 20 , 21
				else // 추출한 문자열이 0으로 시작하거나 시작하지 않는 경우 EX) 0020, 021, 20, 21
				{
					for (int j = 0; j < num.size(); j++)
					{
						if (num[j] == '0')
						{
							continue;
						}
						else
						{
							num = num.substr(j, num.size() - j + 1);
							result.push_back(num);
							break;
						}
					}
					i--; // 추출한 문자열 다음 문자열 부터 다시 탐색
					continue;
				}
			}
		}
	}

	sort(result.begin(), result.end(), stringNumCmp); // string 형태의 문자열 오름차순 배열
	for (auto c : result)
	{
		cout << c << '\n';
	}

}