[백준]_10610번 : 30(파이썬 and C언어)

 

10610번: 30

처음에 문제를 접했을 때 조금 쫄았다. 왜냐하면 요구 사항들 간의 연관성이 별로 없기 때문이다. 30의 배수인지도 확인하고 수들을 조합해서 만들 수 있는 숫자의 최댓값을 출력해라라니..

 

그래도 각 조건들이 요구하는 것이 무엇인지 알 수만 있다면 쉽게 풀리는 문제이다.

---

조건 파악

일단 어떤 수가 30의 배수이려면 2의 배수이면서 3의 배수이면서 5의 배수이어야 한다. 하지만 이것을 전부 연산하기에는 좀 그렇다;; 그래서 단계를 조금 줄여보자. 만약에 1의 자리 숫자가 0인 수는 반드시 10의 배수이다. 이것은 즉 2의 배수이면서 5의 배수임을 1의 자리가 0인지만 관찰하면 알 수 있다는 것이다!!

따라서 입력값, 가령 그 숫자가 102이면 1, 0, 2 중에 0이 있기 때문에 입력값에 포함된 숫자들을 섞어 10의 배수를 만들 수 있음을 알 수 있다. 마지막으로 3의 배수임을 알기 위해서 어쩔 수 없이 (각 자릿수의 숫자의 총합)%3==0 을 만족하는지 알아봐 줘야 한다.

 

이제 30의 배수 조건을 통과 했으면 어떻게 해야 할까? 숫자들을 조합해서 최대의 정수를 만들어야 하기 때문에 숫자들을 내림차순으로 정렬하고 그 결과를 출력하면 되는 것이다! 왜냐하면 자릿수가 높은 위치에 최대한 큰 숫자를 배정하는 것이 최댓값을 만드는 데에 장땡이기 때문이다.

 

시도 1(Python)

import sys
input = sys.stdin.readline

num=list(input().strip())
arr=[]
for i in num:
    arr.append(int(i))
arr.sort()
if arr[0]!=0:
    print(-1)
elif sum(arr)%3!=0:
    print(-1)
else:
    arr.sort(reverse=True)
    print(''.join(str(n) for n in arr))

<평가> 나중에 와서 과거 코드를 보니까 그래도 뭔가 더 짧게 줄이고 싶은 생각이 든다..

수정

이미 num으로 수를 입력 받았는데 단지 정수형으로 입력받고 싶다고 해서 리스트를 또 선언(arr) 해주는 것은 무리인 것 같다. 차라리 num을 지우고 arr만 사용하겠다.

import sys
input = sys.stdin.readline

arr=list(input().strip())
arr=sorted(arr, reverse=True)

아니면 이렇게까지 줄일수도..

arr = sorted(list(input().strip()), reverse=True)

---

 

먼저 arr에 '0'이 포함되어 있는지 확인한다. 여기서 if '0' not in arr: print(-1)을 해도 되지만 이렇게 하면 arr의 모든 요소들을 검사해서 '0'이 있는지 확인해야 하기 때문에 비효율적이다. 우리가 확인해줘야 할 요소는 오직 마지막임을 잊지 말자.

if int(arr[-1])!=0:
    print(-1)

---

아직 arr에는 문자형 변수들만 남아 있어서 3의 배수인지 확인하기 어렵다(자릿수의 총합을 구해야 하기 때문). 따라서 아래와 같은 과정을 거쳐주자.

else:
    total = 0
    for i in arr:
        total += int(i)
    if total % 3 != 0:
        print(-1)
    else:
        print(''.join(arr))

최종 코드

import sys
input = sys.stdin.readline

arr = sorted(list(input().strip()), reverse=True)

if int(arr[-1]) != 0:
    print(-1)
else:
    total = 0
    for i in arr:
        total += int(i)
    if total % 3 != 0:
        print(-1)
    else:
        print(''.join(arr))

---

시도 2(C언어)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int compareDesc(const void *a, const void *b) {
    return (*(int *)b - *(int *)a);
}
int main() {
    char num[100001];
    int arr[100001];
    int digit=0;
    scanf("%s", num);
    for (int i=0;i<strlen(num);i++) {
        if (num[i]>='0' && num[i]<='9') {
            arr[digit]=num[i]-'0';
            digit++;
        }
    }
    qsort(arr, digit, sizeof(int), compareDesc);
    if(arr[digit-1]!=0) printf("-1");
    else{
        int sum=0;
        for (int i = 0; i < digit; i++) {
            sum+=arr[i];
        }
        if(sum%3!=0) printf("-1");
        else
            for (int i = 0; i < digit; i++) {
                printf("%d", arr[i]);
            }
    }
    return 0;
}

<평가> 코드를 파이썬에서 C로 전환시키면서 가장 어려웠던 점은 입력받는 숫자가 최대 100000자리 숫자라는 점이다. 이것은 애초에 숫자로 접근하는 방법을 배제하라는 협박(?)이다.필자는 처음에 int(미쳤다..) 로 숫자를 받고 10으로 나눈 나머지를 배열에 저장하고 10으로 나눈 몫을 기존 값에 다시 대입하고 이것을 반복하는 방식을 채택했다가 장렬히 전사하였다. 이해를 돕기 위해 아래에 코드를 첨부하겠다.

int num;
int arr[100001];
int digit=0;
scanf("%d",&num);
while(num>0){
arr[digit]=num%10;
num/=10;
digit++;
}