[알고리즘] 백준 10610번_30 문제풀이 (Python 파이썬)

 

10610번: 30

문제상황

입력받은 숫자를 배열해서 30의 배수가 되는 가장 큰 수를 만든다.

 

구하고자 하는 것

30의 배수가 되는 가장 큰 수 (없으면 -1)

 

입력

0으로 시작하지 않는 최대 10^5개의 숫자로 구성된  N

 

IDEA

30의 배수 = 3의 배수 * 10의 배수 로 나눠서 생각해보면

내가 입력받은 수에 0이 있어야지 10의 배수를 만족할 수 있다.

또한 3의 배수가 될 조건은 각 자리의 숫자를 모두 더했을 때 3의 배수이면 3의 배수

 

• 30의 배수를 판단하는 과정에서 숫자 자체로 다루기 보다는 각 숫자 자릿수를 개별적으로 판단하므로 문자열로 처리
• 입력받은 숫자 문자열의 각 자릿수를 숫자형 리스트로 저장 후 내림차순 정렬
• 가장 마지막 요소가 0이면 3의 배수임을 체크 (리스트의 모든 요소의 합이 3으로 나눠떨어지는가)
• 3의 배수라면 리스트에 저장된 값을 차례로 이어붙혀서 출력

 

Code

N = input()

ls = [int(i) for i in N]
ls.sort(reverse=True)


if ls[-1] != 0:
  print(-1)
elif sum(ls) % 3 != 0:
  print(-1)
else :
  print(''.join([str(i) for i in ls]))