[C++] 백준(BOJ) - 2870 : 수학숙제
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
상근이는 수학시간에 딴 짓을 하다가 선생님께 걸렸다. 선생님은 상근이에게 이번 주말동안 반성하라며 엄청난 숙제를 내주었다.
선생님이 상근이에게 준 종이에는 숫자와 알파벳 소문자로 되어있는 글자가 N줄있다. 상근이는 여기서 숫자를 모두 찾은 뒤, 이 숫자를 비내림차순으로 정리해야한다. 숫자의 앞에 0이 있는 경우에는 정리하면서 생략할 수 있다.
글자를 살펴보다가 숫자가 나오는 경우에는, 가능한 가장 큰 숫자를 찾아야 한다. 즉, 모든 숫자의 앞과 뒤에 문자가 있거나, 줄의 시작 또는 끝이어야 한다.
예를 들어, 01a2b3456cde478에서 숫자를 찾으면 1, 2, 3456, 478이다.
선생님이 준 종이의 내용이 주어졌을 때, 상근이의 숙제를 대신하는 프로그램을 작성하시오.
입력
첫째 줄에 종이의 줄의 개수 N이 주어진다. (1 ≤ N ≤ 100)
다음 N개의 줄에는 각 줄의 내용이 주어진다. 각 줄은 최대 100글자이고, 항상 알파벳 소문자와 숫자로만 이루어져 있다.
출력
종이에서 찾은 숫자의 개수를 M이라고 하면, 출력은 M줄로 이루어져야 한다. 각 줄에는 종이에서 찾은 숫자를 하나씩 출력해야 한다. 이때, 비내림차순으로 출력해야 한다. 비내림차순은 내림차순의 반대인 경우인데, 다음 수가 앞의 수보다 크거나 같은 경우를 말한다.
예제 입력
2
lo3za4
01
예제 출력
1
3
4
알고리즘
- 문자열
- 정렬
- 파싱
풀이
- 100자리의 수 long long 형으로도 커버가 안된다
- string 형으로 풀이 후 변환
- 숫자를 덧붙여 나가며 문자열을 만들어나가는 logic
- 숫자 맨앞에 붙은 0을 제거하는 logic
- 매개변수 참조로 전달(값 직접 변환)
- ‘0000’과 같은 수 모두 사라졌을 때 반례 check
- string의 비내림차순 custom operator 구현
코드
// 문자열
#include <bits/stdc++.h>
using namespace std;
int n;
vector<string> v;
void go(string &tmp) // 참조로 전달 => 값을 직접 변환 가능하다
{
while (true)
{
if (tmp.size() && tmp.front() == '0') tmp.erase(tmp.begin()); // 앞부분 0 이라면 제거
// front를 참조하기 이전에 size를 체크해야 한다(참조 에러 방지)
else break;
}
if (tmp.size() == 0) tmp = "0"; // 모두 제거 되었다면 원래 숫자는 0이다
v.push_back(tmp); // 배열에 담기
tmp = ""; // 빈 문자열로 다시 초기화
return;
}
// string의 비내림차순 Custom Operator
bool cmp(string a, string b)
{
if (a.size() == b.size()) return a < b;
return a.size() < b.size();
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
string tmp = "";
for (int j = 0; j < str.size(); j++)
{
// 만약 숫자라면 string 형 tmp 변수에 더해나감
if (isdigit(str[j])) tmp += str[j];
// 문자를 만났을 때 go 함수 발동
else if(tmp.size()) go(tmp);
}
// 숫자로 남고 끝났을 때 실행
if (tmp.size()) go(tmp);
}
sort(v.begin(), v.end(), cmp);
for (auto i : v) cout << i << '\n';
return 0;
}
평가
- 숫자가 큰 문제의 경우 string으로 풀 생각을 할 수 있어야한다
- string 형으로 만든 숫자의 대소 비교는 cmp를 만들어서 비교한다
- 참조로 매개변수를 받는 것에 대해 익숙해 질 정도로 연습이 필요하다
- string 형의 front, end 등 지점을 참조 할때는 항상 size가 0이 아닌지를 확인하여서 참조 에러를 없애야 한다
- 반례를 생각하자
