Python 백준 10610번 - 30 (시간 초과 해결)

문제

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

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

입력

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

출력

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

 

나의 생각

이 문제를 보고 몇 가지 조건들이 떠올랐다.

1. 30, 150, 180.. 이렇게 끝자리가 0으로 반드시 끝나야 한다는 것

2. 입력한 값의 자리 수보다는 배수가 될(출력) 것의 길이가 크거나 같아야 한다는 것

3. 어느 정도 규칙성은 존재했다는 것. 구구단 3단을 기준으로 나눠 볼 수 있었던 것

어쨌든 이 정도 떠올라서 입력하는 값의 모든 조합의 수를 구한 다음 이 조합들 중에 정렬, 나열 후 큰 수 인 가장 뒤에부터 30으로 나누어서 0이 되면 배수니까 그중 맞는 것을 출력하면 되겠다고 생각을 하였다.

여기서 문제점, N의 자릿수가 무려 10^5 개의 자릿수로 되어 있어, ex) 102만 해도, 10, 20, 21, 12 ,,, 기하급수적으로 증가한 다는 것. 그래서 다른 방법을 생각해보았다.

그렇다면 상대적으로 30의 배수인 30, 150, 180 이렇게 수가 증가하면서 각 자릿수에 존재하는 수의 개수를 저장해 두고 입력한 N 의 숫자들의 자리수와 갯수를 세어서 비교한 후 일치하면 30의 배수라는 알고리즘을 생각하였다. 그래서 이 문제에 핵심은 큐인가?라는 생각이 들었다. 그래서 구현해 보았다.

 

코드 1

import sys
N = list(str(int(sys.stdin.readline().rstrip())))
start, idx = 30, 1
numbers = {}
result = []
for i in N:
    if i in numbers:
        numbers[i] += 1
    else:
        numbers[i] = 1
 
while len(list(str(start * idx))) <= len(N):
    A = start * idx
    result.append(A)
    flag = False
    A = list(str(A))
 
    for a in A:
        if str(a) not in numbers:
            result.pop()
            flag = True
            break
        elif numbers[str(a)] != A.count(a):
            result.pop()
            flag = True
            break
    if flag == False and len(result) != 1:
        result.pop(0)
    idx += 1
 
print(-1 if not result else result[0])

결과 1

역시나 시간 초과가 났다. 연산 과정이 너무 많은 것이 문제였다. 입력 예시들의 경우 결과는 잘 나왔지만, 문제에서 원하는 방향이 아닐 것이다.

 

방안

생각을 더 해보다가 도저히 규칙성은 찾지 못하겠다고 생각이 들어, 다른 사람들의 생각을 참고하였다. (물론 코드는 보지 않았다.) 하여, 알게 된 것은 30의 배수는 각 자릿수의 합이 반드시 3의 배수여야 한다는 것,, 생각보다 단순하였다. 그리고 끝자리가 0이면 된다는 것. 이 것은 위에서도 혼자 생각했던 것이었는데, 하나만 더 생각했으면 쉽게 풀렸을 문제였다. 

 

코드 2

import sys
N = list(str(int(sys.stdin.readline().rstrip())))
N = sorted(N, reverse=True)
 
if sum(map(int, N)) % 3 != 0 or N[len(N)-1] != '0':
    print(-1)
else:
    print(int(''.join(N)))