[python] 백준 10610 : 30

[python] 백준 10610 : 30

10610번: 30 (acmicpc.net)

10610번: 30

실버 5

그리디

---

접근

N의 입력값 크기나 너무나 크기 때문에 안의 숫자들을 어떻게 바꿔야할지 고민이 많았는데

그냥 다음의 조건들을 참고하면 쉽게 풀 수 있었다.

 

N이 3의 배수임을 확인하는 법 : 각 자릿수의 총합이 3의 배수면 N은 3의 배수이다.

30의 배수를 찾아야 하기 때문에 N의 숫자 중에 0이 없으면 -1을 출력하도록 한다.

 

두 조건을 만족하는 숫자는 순서를 바꾸어도 30의 배수가 되기 때문에 내림차순으로 출력하면 된다.

(각 자리의 수의 합이 3의 배수라면 순서를 바꾸어도 어차피 총합이 3의 배수이기 때문.)

자세한 이론은 배수 판별법을 검색해보자.

 

코드1

import sys;
N = sorted(sys.stdin.readline().rstrip(), reverse=True)

sum = 0
zero = False
for i in range(len(N)):
    sum += int(N[i])
    if int(N[i]) == 0:
        zero = True

if zero == True and sum % 3 == 0 :
    for n in N:
        print(n, end='')
else: 
    print(-1)

반복문을 돌면서 각 자리수의 총합을 계산하고 0이 있을 경우 True값을 주었다.

만약 zero값이 True이고 3의 배수임이 확인되었다면 N의 내림차순한 값을 출력했다.

 

위의 코드는 모든 케이스가 O(2N)이 걸린다는 문제가 있다.

만약 입력한 숫자에 0이 없음이 바로 확인된다면 sum%3==0과정 없이도 print(-1)을 출력하면 되기 때문에 아래와 같이 코드를 개선할 수 있다.

 

개선한 코드

import sys;
N = sorted(sys.stdin.readline().rstrip(), reverse=True)
sum = 0

if '0' not in N:
    print(-1)
else:
    for i in N:
        sum += int(i)

    if sum % 3 == 0:
        print(''.join(N))
    else: print(-1)

N은 리스트 형태로 저장되어 있기 때문에 join함수를 써서 공백없이 각각의 값을 출력하도록 했다.

0이 없는 숫자는 반복문 한번에 프로그램이 종료되기 때문에 O(N)으로 끝낼 수 있는 케이스가 존재하여 시간을 약간이나마 줄일 수 있었다.