BOJ_10610 : 30

김진현·2021년 7월 2일

BOJ

목록 보기

17/33

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

문제

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

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

입력

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

출력

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

아이디어

정수를 입력받으면 그 수를 자릿수대로 분할하고, 조합을 역순으로 정렬한다.
역순 조합을 다시 자릿수를 맞춰서 정수로 변환한다
새로 만들어진 정수가 30으로 나누어떨어지는지 순차적으로 검사한다.
조건에 맞는 수가 있으면, 검사를 종료한다.

코드

Mine (시간 초과)

import sys
from itertools import permutations

input = lambda : sys.stdin.readline()

N = int(input())
N_len = len(str(N)) # 자릿수 저장
N_list = []

dec = 10**(N_len-1)
while dec:
    N_list.append(int(N // dec))
    N = N % dec
    dec = dec // 10

permute = list(permutations(N_list,N_len)) #조합 저장
permute.sort(reverse=True) #역순으로 sort

for case in permute:
    result = -1
    dec = 10 ** (N_len - 1)
    Num = 0

    #조합 -> 정수 변환
    for i in range(N_len):
        Num += case[i] * dec
        dec //= 10

    if Num % 30 == 0:
        result = Num
        break
print(result)

개선사항

늘 그렇듯이 결과값은 나오지만 시간초과가 떴다.
30은 10과 3의 곱이다.
입력받은 숫자의 합이 3의 배수이고, 0이 존재한다면, 30의 배수인가?

Mine(시간초과)

import sys
input = lambda : sys.stdin.readline()

N = int(input())
N_len = len(str(N)) # 자릿수 저장
N_list = []
is_valid = 0
dec = 10**(N_len-1)

while dec:
    T = int(N // dec)
    N_list.append(T)
    N = N % dec
    dec = dec // 10

    #10의 배수인지 검사
    if T == 0:
        is_valid = 1

N_list.sort(reverse=True) #역순으로 sort

#10의 배수인 수이면서 3의 배수인지 검사
if is_valid:
    if sum(N_list) % 3 == 0:
        dec = 10 ** (N_len - 1)
        Num = 0
        for i in range(N_len):
            Num += N_list[i] * dec
            dec //= 10
        print(Num)

    else:
        print('-1')
else:
    print('-1')

개선사항

2번째 함수는 유지하면서
input된 수의 자릿수를 저장하는 방식을 바꾼다.
처음부터 int로 받아, 자릿수마다 10의 배수로 나눠주는 게 아니라
string으로 받아서, 각 자릿수를 뽑아낸다.

Mine(시간초과)

import sys
input = lambda : sys.stdin.readline()

N = int(input())
N_len = len(str(N)) # 자릿수 저장
N_list = []
is_valid = 0
dec = 10**(N_len-1)

while dec:
    T = int(N // dec)
    N_list.append(T)
    N = N % dec
    dec = dec // 10

    #10의 배수인지 검사
    if T == 0:
        is_valid = 1

N_list.sort(reverse=True) #역순으로 sort

#10의 배수인 수이면서 3의 배수인지 검사
if is_valid:
    if sum(N_list) % 3 == 0:
        dec = 10 ** (N_len - 1)
        Num = 0
        for i in range(N_len):
            Num += N_list[i] * dec
            dec //= 10
        print(Num)

    else:
        print('-1')
else:
    print('-1')

clone

n = int(input())
nums = list(str(n))
nums.sort(reverse=True)

def solve(nums):
	if nums[-1] ! = '0':
		return -1
	if sum(map(int, nums)) % 3 != 0:
    	return -1
    return int(''.join(nums))
print(soleve(nums))