문제
어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.
미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.
입력
N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.
출력
미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.
풀이
풀이 전 메모
입력받은 숫자를 내림차순으로 정렬한다. --> 입력받은 숫자를 조합하여 나올 수 있는 최대값을 뽑기 위함이다.
그 수를 30으로 나눴을때 나머지가 0이면, 30의 배수이다.
또한 30의 배수는, 3의 배수이자, 10의 배수인 조건이 필요하다.
뽑은 최대값으로부터 1씩 빼가면서, 3의 배수와 10의 배수의 조건에 부합하면
출력해보자.
풀이 중 알아본 내용
1의 배수: 모든 수는 1의 배수이므로 굳이 계산 필요가 없다.
2의 배수는 일의 자리의 수가 0, 2, 4, 6, 8 이다.
3의 배수는 모든 자리의 수의 합이 3의 배수이다.
4의 배수는 가장 끝에 두 자리수가 00이거나 4의 배수인 수이다. (십의 자리가 짝수인 경우에는 일의 자리수가 0, 4, 8이면 되고, 십의 자리수가 홀수인 경우에는 일의 자리수가 2, 6이면 된다.)
5의 배수는 일의 자리수가 홀수면 5, 짝수면 0인 수이다.
6의 배수는 2와 3의 공배수, 즉, 짝수이면서 각 자리의 합이 3의 배수인 수이다.
7의 배수는 일의 자리를 두 배 한 것을 나머지 수에서 빼면 결과가 0 또는 7의 배수가 나오는 수이다.[1](스펜스의 방법) 다른 방법으로는 일의 자리부터 세 자리씩 끊어서 교대로 빼고 더한 것이 7의 배수일 경우 본래의 수도 7의 배수이다. 이 방법은 7이 1001의 약수임을 이용한 것으로 다른 1001의 약수 11, 13, 77, 91, 143, 1001에도 적용시키는 게 가능하다. 또 다른 방법으로는 본래의 수를 10으로 나눈 뒤에 소수점 아래는 버림한 값에 본래의 수의 일의 자리를 다섯 배한 수를 더한 결과가 7의 배수이면 본래의 수도 7의 배수이다.
8의 배수는 가장 끝에 세 자리수가 000이거나 8의 배수인 수이다. (좀 더 쉽게 설명하자면 백의 자리가 0이거나 짝수인 경우에는 끝에 두 자리수가 00, 08, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96 다시 말해 8의 배수인 수이고, 백의 자리가 홀수인 경우에는 끝의 두 자리수가 4의 배수면서 8의 배수가 아닌 두 자리수 4, 12, 20, 28, 36, 44, 52, 60, 68, 76, 84, 92이어야 한다.)
9의 배수는 각 자리 숫자의 합이 9의 배수인 수이다.
**10의 배수는 일의 자리가 0인 수이다.**변수
n : 입력값
max_value = 입력값으로 도출할 수 있는 최댓값For-Loop 1. Input
최댓값의 조합이 들어있는 문자열 타입을 담고있는 배열을 하나씩 순회한다.
이를 순회하면서 max_value 에 담아준다.
--> list to string 으로 변환하기 위한 과정임
If - 30의 배수 판별
최댓값이 30으로 나눠지면 max_value 출력
아니면 -1 출력
CODE - 실패(시간초과)
import sys
input = sys.stdin.readline
n = list(input().strip())
n = sorted(n, reverse=True)
max_value = str()
for item in n:
max_value += item
max_value = int(''.join(max_value))
for i in range(max_value, 0, -1):
if max_value % 30 == 0:
print(max_value)
break
elif i < 30:
print(-1)
break최댓값으로부터 -1 씩하면서, 배수 판별을 한다.
다음과 같은 코드는 O(N) 의 시간복잡도를 가지지만...
시간제한은 1초이고
최대 입력값의 크기인 10^5 만큼의 크기를 하나씩 순회하게되면서 시간초과가 난다.
CODE - 성공
import sys
input = sys.stdin.readline
n = list(input().strip())
n = sorted(n, reverse=True)
max_value = str()
for item in n:
max_value += item
max_value = int(''.join(max_value))
if max_value % 30 == 0:
print(max_value)
else:
print(-1)솔직하게 말하면 에라 모르겠다하고 제출한 코드인데 정답이 됐다...
최댓값 말고 그 아래 숫자들은 배수 판별을 안해도 되는건가...? 최댓값이 30의 배수가 아니면 다른 숫자는 30의 배수라고 볼 수 없는건가?