[그리디 알고리즘] ★ 10610번 - 30

[백준] 10610번 - 30

(풀이1) 정답 코드

1) 문제 해결 아이디어

해당 문제는 3의 배수임을 판별하는 조건을 알고 있으면 쉽게 풀 수 있는 문제였다.

배수 판별법에 따라 3의 배수는 각 자리의 숫자의 합이 3의 배수인 수이다.

 

<30의 배수가 되는 조건>

- 일의 자리수가 0

- 각 자리의 숫자들의 합이 3의 배수

 

일단 입력한 문자열을 리스트로 변환하여 내림차순 정렬하는 것이 포인트다.

30의 배수가 되는 조건 2개를 다 만족한다면 최댓값은 내림차순으로 정렬한 값이 될 것이다.

 

[참고] https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=sctivcrmnfe&logNo=220859963688 

3. (2,3,4,5,6,8,9) 배수 판별법 및 증명-1

 

2) 소스코드

n = list(input()) 
n.sort(reverse=True)  # 내림차순 정렬
sum = 0  # 자리수들의 합

# 자리수 합 구하기
for i in n:
  sum += int(i)

# 자리수의 합이 3의 배수이고, 일의 자리수가 0이면
if(sum % 3 == 0 and "0" in n):
  print(''.join(n))
else:
  print(-1)

 

(풀이2) 메모리 초과된 실패 코드

1) 문제 해결 아이디어

처음 시도한 방법으로 메모리 초과가 되어 실패했다.

입력받은 문자열을 내림차순으로 정렬하고 맨 뒷자리가 0이면 0을 떼고 아니면 30의 배수가 될 수 없으므로 -1을 시키고 바로 종료한다. (0을 하나 떼서 테스트 케이스 수를 줄이기 위함)

permutations 라이브러리를 사용하여 순열을 리스트로 얻는다.

 for문에서 리스트 안의 튜플을 문자열->정수형 변환한 후 3의 배수인지 검사하여 맞다면 바로 출력시키고 탈출한다. (아까 0을 제거했기 때문에 30의 배수가 아닌 3의 배수인지를 검토한다.) 마지막까지 해당 조건문을 만족하지 못하면 -1을 출력 시킨다.

 

2) 소스코드

from itertools import permutations

n = str(input())  # 양수 n
n = ''.join(sorted(n, reverse=True))  # 내림차순 정렬

# 맨 마지막 인덱스가 0이 아니면 종료
if(n[len(n) - 1] != "0"):
  print("-1")
  exit()

# 뒤에 0 하나 제거
n = n[0:len(n)-1]

# 순열 리스트 (nPn = n!) 
arr = list(map(''.join, permutations(n, len(n))))

for i in range(len(arr)):
  # 튜플을 문자열로 변환
  #num = ''.join(arr[i])
  # 탈출 조건
  if( int(arr[i]) % 3 == 0):
    print(arr[i] + "0")
    break
  if(i == len(arr) - 1):
    print(-1)
    break

 

[참고] https://www.delftstack.com/ko/howto/python/tuple-to-string-python/#str.join%25ED%2595%25A8%25EC%2588%2598%25EB%25A5%25BC-%25EC%2582%25AC%25EC%259A%25A9%25ED%2595%2598%25EC%2597%25AC-python%25EC%2597%2590%25EC%2584%259C-%25ED%258A%259C%25ED%2594%258C%25EC%259D%2584-%25EB%25AC%25B8%25EC%259E%2590%25EC%2597%25B4%25EB%25A1%259C-%25EB%25B3%2580%25ED%2599%2598

Python에서 튜플을 문자열로 변환