백준 10610번 30 풀이(c++)

문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

 

해당문제를 처음 풀때는 처음받는 숫자를 string 에 넣은 후 해당 숫자들을 내림차순으로 정렬 한 뒤 가장뒤에 작은 숫자부터 오름차순으로 다시 정렬하면서 30의 배수가 있나 탐색을 하였다. 이때 테스트케이스는 통과를 했으나 제출시 런타임 에러 혹은 시간초과가 되었고 그 이유는 엄청 큰 숫자가 들어오면 탐색이 오래걸릴 뿐더러 string 을 int 로 바꿔주는 stoi함수를 사용했는데 그 함수가 숫자의 사이즈를 감당하지 못하기 때문이었다.

 

그래서 결론적으로 30의 배수는 일의자리는 무조건 0일테니 1의자리가 0이면 -1 리턴, 이후 0을 빼고 나머지값을 더했을때 3의 배수면 해당 값을 출력하도록 프로그래밍 했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int main()
{
    string input;
    cin >> input;
    sort(input.begin(), input.end(), greater<>());

    if (input[input.length() - 1] != '0')
        cout << -1;
    else
    {
        long long sum = 0;
        for (auto o : input)
        {
            sum += o - '0';
        }
        if (sum % 3 == 0)
            cout << input;
        else
            cout << -1;
    }
}