[10610번] 30

문제 출처 : 

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 30의 배수를 찾는 방법

2. 30의 배수일 때 정렬하는 방법

이 두가지를 파악한다면 알고리즘을 풀 수 있다.

우선 30의 배수를 찾는 방법은 다음과 같다.

3의 배수를 찾아 그 뒤에 0만 붙이면 30의 배수이다.

3의 배수는 각 자리 숫자의 합이 3의 배수이면 3의 배수이다. 

예를들어 12는 1+2 = 3이므로 3의 배수이지만

13은 1+3 = 4이므로 3의 배수가 아니다.

그리고 30의 배수를 찾았을 때 정렬하는 방법은 다음과 같다.

그냥 버블정렬로 하기에는 O(n^2)이 되므로 시간 복잡도가 너무 높아지게 되고,

다른 방법으로는 0부터 9까지로만 수가 존재하니 9가 나오는 것들을 다 출력하고 ... 0이 나오는 것들을 다 출력하면 된다.

예를들어 9133190은 30의 배수인데 이것을 위의 방법대로 한다면

99 -> 9933 -> 993311 -> 9933110으로 출력될 것이다.

소스 코드 : 

#include <stdio.h>
#include <string.h>
 
int main()
{
    int sum = 0, len, cnt = 0, check = 0;
    char arr[100001];
 
        scanf("%s", arr);
        len = strlen(arr);
 
        for (int i = 0; i < len; i++)
        {
            if (arr[i] == '0')
            {
                check = 1;
                // 예외처리 : 길이가 1이고 그 값이 0이면 즉,  0뿐일 때
                if (len == 1)
                {
                    printf("-1");
                    return 0;
                }
                //  예외처리 : 길이가 1보다 크지만, 첫번째 수가 0일때 즉, 0123이런 수가 들어왔을 때
                if (arr[0] == '0' && len > 1)
                {
                    printf("-1");
                    return 0;
                }
            }
        }
        
        if (check == 1)
        {
            for (int i = 0; i < len; i++)
                sum = sum + (int)(arr[i] - 48); // 각 자리 수의 합을 구한다.
 
            if (sum % 3 == 0) // 각 자리 수의 합이 3의 배수라면?
            {
                for (int j = 9; j >= 0; j--)
                {
                    for (int k = 0; k < len; k++)
                    {
                        if (arr[k] == j+48) // 아스키 코드를 이용
                        {
                            printf("%c", arr[k]);
                            cnt++;
                        }
                        if (cnt == len) 
                            break;
                    }
                }
            }
            else
                printf("-1");
        }
 
        else
            printf("-1");
        
        return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

참고로 이 코드에서

if(cnt == len) break; 이 존재하는 것과 존재하지 않을 때에는 시간 복잡도 차이가 나타난다.

예를들어 9099일 때 999 -> 9990 후 나머지 0 뒤의 99는 비교해도 되지 않아도 되도록 하는 코드이다.

근소한 차이지만, 값이 커질수록 시간 복잡도 또한 커질 것이다.