[그리디] 백준_30

https://www.acmicpc.net/problem/10610

10610번: 30

이 문제를 보고 처음 든 30의 배수임을 확인하는 방법은 다음과 같다.

아이디어: 모든 문자 조합 만들기 -> 30으로 나눠서 떨어지는지 확인 -> 제일 큰 지 확인... 그리디?

그리디 문제인데 위와 같이 구하면 무조건 시간 초과가 날 거 같아 30의 배수임을 확인하는 다른 방법을 생각해 봤다.

아이디어 

30의 배수는 3과 10의 배수이어야 함. 

10의 배수이려면 끝자리가 0이어야 함.

3의 배수이려면 각 자릿수의 합이 3의 배수이어야 함.

위 조건을 만족한다면 30의 배수이기 때문에 sorted함수를 통해 가장 큰 수를 만들고 문자열로 결합하기 위해 join을 통해 문자열로 만들어줬다.

문자열은 변경 불가능한(immutable) 자료형이기 때문에 sort함수로는 정렬하지 못합니다. 이는 문자열이 생성된 후에는 해당 문자열을 수정할 수 없음을 의미합니다. 문자열의 각 문자를 정렬하는 것은 새로운 문자열을 만드는 것이므로 문자열에 대해서는 sort 함수를 사용할 수 없습니다.

https://blu-blu.tistory.com/3

[그리디] 모험가 길드 + input(), sort(), sorted()

위 글에서도 알 수 있지만 sorted 함수는 어떠한 이터러블 객체에도 적용 가능하기 때문에 문자열을 정렬하고 싶다면 sort가 아닌 sorted함수를 사용해야 합니다.

sorted함수로 문자열을 정렬하면 문자열의 각 문자를 원소로 하는 리스트를 반환합니다. 따라서 이를 join 함수를 통해 다시 문자열로 결합해주어야 합니다.

아래는 제가 푼 정답 코드입니다.

#백준 10610 30
import sys
input=sys.stdin.readline

n=input().strip()

#아이디어:30의 배수는 3과 10의 배수이어야 함. 10의 배수이려면 끝자리가 0이어야 함. 3의 배수이려면 각 자리수의 합이 3의 배수이어야 함.

if '0' not in n:
  print(-1) #끝자리가 0이 아니면 30의 배수가 아니므로 바로 -1리턴
elif sum(map(int,n))%3!=0:
  print(-1) #각 자리수의 합이 3의 배수가 아니면 30의 배수가 아니므로 바로 -1리턴
else: #30의 배수
  print(''.join(sorted(n, reverse=True)))

에버랜드를 갔다 온 후로 14시간을 자느라 어제 1일 1코를 못했다..ㅎ

오늘은 꼭 1코를 하기 위해 무거운 몸을 이끌고 컴퓨터에 앉아서 그리디 문제를 풀어보는데

확실히 실버문제여서 매우 쉬움을 느껴서 갱장이 뿌듯했다!! 희희~

골드냥~