주어진 수 N에 포함된 수를 섞어 30의 배수가 되는 가장 큰 수를 만드는 문제.
N의 자릿수가 최대 100,000이므로 정수로 입력받지는 못하고 string으로 입력을 받아야 한다. 그리고 나서 가장 큰 수를 구하는 것이기 때문에 string의 element들을 내림차순으로 정렬한 후 30의 배수인지를 확인하면 된다.
30은 10*3이므로 10의 배수이면서 동시에 3의 배수인지를 확인한다. 10의 배수는 0으로 끝나는지만 확인하면 되고, 모든 자릿수의 합이 3의 배수이면 3의 배수인지를 쉽게 판별할 수 있다.
쉬운 문제였으나 수의 범위라던지 등등의 내용을 꼼꼼히 확인하고 풀어서 뿌듯했다. 그리고 string 안에서도 sort()를 사용해 내부 element들을 정렬할 수 있다는 것을 알게되었다. 나중에 문제풀 때 유용하게 써먹을 수 있을 것 같다
#include <iostream>
#include <string>
#include <algorithm> // sort
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
string N; // N이 최대 100,000개의 숫자로 구성됐기 때문에 str로 입력 받기
cin >> N;
int i;
int size = N.size();
// sort in descending order
sort(N.begin(), N.end(), greater<char>());
// 30의 배수인지 검사. 30 == 10 * 3이므로 10의 배수이며 3의 배수인지 체크하면 된다.
if (N[size - 1] == '0') { // 10의 배수인지 검사
// 3의 배수인지 확인
// 모든 자리수를 다 더한 값이 3의 배수면 그 수도 3의 배수이다.
int cnt = 0; // 최댓값이 9 * 10^5니까 int로 선언해도 됨
for (i = 0; i < size; i++) cnt += (N[i] + '0');
if (cnt % 3 == 0) cout << N << endl; // 10의 배수 && 3의 배수
else cout << -1 << endl; // 10의 배수 && !3의 배수
}
else cout << -1 << endl; // !10의 배수
return 0;
}