문제 링크
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';
}
}
'CS(Computer Science)지식 > [C++][코딩 테스트] 자료구조 및 알고리즘' 카테고리의 다른 글
[C++] 백준 2999번: 비밀 이메일 (0) | 2024.02.04 |
---|---|
[C++] 백준 1969번: DNA (0) | 2024.02.04 |
[C++] 백준 3613번: Java vs C++ (0) | 2024.02.04 |
[C++] 백준 9996번: 한국이 그리울 땐 서버에 접속하지 (0) | 2024.02.04 |
[C++] 백준 2941번: 크로아티아 알파벳 (0) | 2024.02.04 |