[Python 알고리즘] 백준 10610번 : 30

문제

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

입력

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

# Case 1
30

# Case 2
102

# Case 3
2931

# Case 4
80875542

출력

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

# Case 1
30

# Case 2
210

# Case 3
-1

# Case 4
88755420

내가 제출한 풀이 - 틀림

import itertools
import sys

n = sys.stdin.readline().strip()
str_list = list(map(int, n))
result = 0

for i in itertools.permutations(str_list):
    # 앞자리가 0은 제외
    if i[0] == 0:
        continue

    num = int(''.join(list(map(str, i))))

    if num % 30 == 0:
        result = max(result, num)

result = (result if result != 0 else -1)

print(result)

itertools라는 라이브러리를 사용하여 순열을 만들어 사용하였다. 하지만 시간초과가 떠서 맞추지 못했다. 아마, 모든 경우의 수를 반복하기 때문에 되지 않는 거 같다.

정답

import sys

n = list(sys.stdin.readline().strip())
n.sort(reverse=True)
sum = 0

for i in n:
    sum += int(i)

if '0' not in n or sum % 3 != 0:
    print(-1)
else:
    print(''.join(n))

Tip

30의 배수판별법

각각 숫자의 대한 배수를 판별하는 방법이 있었다. 이것을 배수판별법이라고 부른다. 나는 처음 보는 공식(?)이기도 했다.

30의 배수판별법은

• 일의 자리가 무조건 0이여야 한다.
• 각각 자리마다의 숫자를 다 더하고 3을 나눠 나누어 떨어져야 한다.
• 360을 예로 들어보자.
  
  1. 일의 자리가 0이므로 통과
  2. 3 + 6 + 0 = 9
  3. 9 / 3 = 3 (나누어 떨어짐)
  4. 360은 30의 배수이다.

itertools

itertools는 효율인 루핑을 위한 이터레이터를 만드는 함수이다. itertools는 많은 함수가 있는데, 그 중 많이 사용할 거 같은 함수만 알아보자. 

• combinations()
• combinations_with_replacement()
• product()
• permutations()

모든 함수들은 숫자, 문자의 조합을 이루어준다.

iterable의 순서에 따라 사전식 순서로 방출되기 때문에 iterable이 정렬되어 있다면, 조합 또는 순열 튜플이 정렬된 순서로 생성된다고 Python 공식문서에 나와있다.

 

combinations(iterable, r)

입력 iterable에서 원소 개수가 r만큼의 조합을 반환해줍니다.

import itertools

n_list = [1, 2, 3]

for i in itertools.combinations(n_list, 2):
    print(i)
    
"""
    출력 결과 :
    (1, 2)
    (1, 3)
    (2, 3)
"""

combinations_with_replacement(iterable, r)

입력 iterable에서 원소 개수가 r만큼의 조합을 반환해주지만 조합의 형태가 두 번 이상 반복할 수 있게 됩니다.

import itertools

n_list = [1, 2, 3]

for i in itertools.combinations_with_replacement(n_list, 2):
    print(i)
    
"""
    출력 결과 : 
    (1, 1)
    (1, 2)
    (1, 3)
    (2, 2)
    (2, 3)
    (3, 3)
"""

permutations(iterable, r=None)

입력 iterable에서 원소 개수가 r만큼의 순열을 생성해줍니다.

r이 지정되지 않았거나 None이면, r의 기본값은 iterable의 길이이다.

import itertools

n_list = [1, 2, 3]

for i in itertools.permutations(n_list):
    print(i)
    
"""
    출력 결과 : 
    (1, 2, 3)
    (1, 3, 2)
    (2, 1, 3)
    (2, 3, 1)
    (3, 1, 2)
    (3, 2, 1)
"""

product(*iterables, repeat=1)

여러 iterable의 데카르트곱을 반환해준다.

다른 함수와는 다르게 입력 iterable을 여러 개를 넣어줄 수 있다.

쉬운 이해를 위해 문자를 사용하겠다.

import itertools

str_list1 = ['A', 'B', 'C']
str_list2 = ['A', 'B', 'C']

# itertools.product(str_list1, str_list2, repeat=1) 과 동일
# str_list1과 str_list2를 모든 쌍을 지어 반환
for i in itertools.product(str_list1, str_list2):
    print(i)
    
"""
    출력 결과 :
    ('A', 'A')
    ('A', 'B')  
    ('A', 'C')
    ('B', 'A')
    ('B', 'B')
    ('B', 'C') 
    ('C', 'A')
    ('C', 'B')
    ('C', 'C')
"""

iterable의 자신과의 곱을 계산하려면, repeat 인자를 사용하여 반복 횟수를 지정하면 된다.

import itertools

str_list1 = ['A', 'B', 'C']

# itertools.product(str_list1, str_list1, str_list1, repeat=1) 과 동일
for i in itertools.product(str_list1, repeat=3):
    print(i)

"""
    출력 결과 :
    ('A', 'A', 'A')
    ('A', 'A', 'B')
    ('A', 'A', 'C')
    ('A', 'B', 'A')
    ('A', 'B', 'B')
    ('A', 'B', 'C')
    ('A', 'C', 'A')
    ('A', 'C', 'B')
    ('A', 'C', 'C')
    ('B', 'A', 'A')
    ('B', 'A', 'B')
	 ....
"""