30 - 파이썬 (정렬)

사이트 링크 : https://www.acmicpc.net/problem/10610

 

문제는 아래와 같습니다.

문제

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

입력

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

출력

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

 

예제 케이스는 해당 사이트에 있습니다

 

 

문제 해설 

 

맨 처음에 30의 배수를 구하기 위해서 주어진 숫자의 경우의 수를 구하여 30의 배수인지 매칭을 해보고 answer 라는 배열에 추가해본뒤에 그중 가장 큰 값을 확인하였습니다. 물론 permutation 라이브러리를 이용하여 구할수도 있지만 재귀를 이용하여 구해보고 싶어서 아래와코드를 작성하였습니다. 

 

초기코드 -> 결과 메모리 초과 

n = str(input())
n_list = list(n)

# 재귀로 가져올수 있는 모든 수를 공개 
def recursive_num(total, n_list):
    global answer
    if len(n_list) == 0:
        if int(total) % 30 == 0:
            answer = max(answer, int(total))
        return
    for idx, num in enumerate(n_list):
        recursive_num(total+num, n_list[:idx]+n_list[idx+1:])

answer = 0

for idx, num in enumerate(n_list):
    recursive_num(num, n_list[:idx]+n_list[idx+1:])

print(answer)

 

결국 메모리 초과로 실패를 하게 되었습니다. 어떻게 보면 당연한 결과 입니다 10^5의 숫자가 주어졌을떄 모든 수의 경우의 수를 구하면 정말 많은 숫자가 발생이 되고 이건 메모리 초과로 이어지기 때문입니다. 

 

문제 해결 포인트 

어떻게 하면 30의 배수를 모든케이스를 구하지 않거 어떻게 구할수가 있을까? 

아래 배수 판정법 링크를 보면서 코드를 구현해보도록 했습니다. 

https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95

• 30의 배수는 3의 배수이면서 일의자리수가 0인 수이다
• 3의 배수는 각 자리 숫자의 합이 3의 배수인 수이다.

3의 배수가 되려면 각 자리수의 합이 3의 배수가 되어야 한다면 사실 어떤 숫자가 몇의 자리인지는 중요하지 않고 각 숫자의 합이 3의 배수만 되는지 확인하면 되면 확인을 할수있습니다. 

그리고 3의 배수인 동시에 일의자리가 0인것만 체크하면 30의 배수인지를 확인할수가 있습니다. 

제가 구현한 코드는 아래와 같고 결과는 통과하였습니다. 

n = str(input())
n_list = list(map(int, list(n)))
n_list.sort(reverse=True)
n_str_list = list(map(str, n_list))

# 3의 배수는 각 자리수의 합이 3의 배수이여야함
# 3의 배수이면서 0이 되어야함

if sum(n_list) % 3 == 0 and n_list[-1] == 0:
    print(int("".join(n_str_list)))
else:
    print(-1)