양수 N을 보았다. 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만드시오.
# 틀린 코드
"숫자를 뽑아 뽑은 숫자를 가지고 어떤 수를 만들어라" 라는 문제를 여러번 봤다.
그 때 for문으로 노가다뛰다가 발견한 방법은 permutations 다. "순열"인데 순서를 고려하여 줄세우기라는 개념으로 숫자를 조합한 모든 경우를 구할 수 있다.
이 방법을 사용하여 경우의 수 중 최댓값을 찾아서 출력하였다. 근데 처음보는 메모리초과라는 결과를 받았다. 문제를 다시한번 봤더니 N의 범위가 10^5까지다. 터질만 했네^^
from itertools import permutations
import sys
input = sys.stdin.readline
N = list(input().strip())
N.sort()
numbers = []
if N[0] == "0":
numbers = N[1:]
number = max(list(map(''.join, permutations(numbers))))
print(int(number+"0"))
else:
print(-1)# 정답 코드
모든 경우의 수를 구하는 건 무모한 짓이였다. 다시.
우리는 0이 있는지 확인하고 3의배수인지를 확인해야 한다. 3의 배수를 확인하는 방법이 0빼고 나머지를 3으로 나눠보는 방법밖에 없는가? 각 자릿수를 모두 더한 값이 3의 배수면 그 수는 3의 배수다.
그리고 생각해보니 뽑은 숫자만 쓰는게 아니라 모든 숫자를 사용하여 최댓값을 구하는 것이다. 왜 순열을 썼지?
모든 숫자를 사용할 때 가장 큰 값은 역순으로 정렬 후 붙이면 끝이다.
N = list(input())
N.sort(reverse=True)
int_numbers = list(map(int, N))
if sum(int_numbers) % 3 != 0 or int_numbers[-1] != 0:
print(-1)
else:
print(''.join(N))# 배수
배수 관련 내용은 알아두는 게 좋을 것 같다. 특히 3의 배수 특징은 모르면 못 푸는 경우가 생길 거라고 장담한다.
2의 배수 : 일의 자리가 0, 2, 4, 6, 8인 수. N % 2 == 0
3의 배수 : 각 자리 숫자의 합이 3의 배수인 수. sum(numbers) % 3 == 0
4의 배수 : 가장 끝에 두 자리수가 00이거나 4의 배수인 수이다. (십의 자리가 짝수인 경우에는 일의 자리수가 0, 4, 8이고 십의 자리수가 홀수인 경우에는 일의 자리수가 2, 6이면 된다.)
5의 배수 : 일의 자리수가 홀수면 5, 짝수면 0인 수이다.
6의 배수 : 2와 3의 공배수, 즉, 짝수이면서 각 자리의 합이 3의 배수인 수이다.
N % 2 == 0 and sum(numbers) % 3 == 0
7의 배수 : 일의 자리를 두 배하고 나머지 수를 빼서 해주면 결과가 0 또는 7의 배수인 수에 +1을 한 수
