[그리디 알고리즘] 백준 10610번 30

백준 알고리즘 문제 원본 보기

문제

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

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

---

입력

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

---

출력

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

---

예제 

예제 입력 1	예제 출력 1
30	20
예제 입력 2	예제 출력 2
102	210
예제 입력3	예제 출력3
2931	-1
예제 입력4	예제 출력4
80875542	88755420

---

아이디어

어떠한 수 K가 30의 배수가 되기 위해서는 K가 10과 3의 배수여야 한다.

따라서 K의 모든 자리 수의 합이 3의 배수이며, K의 마지막 자리는 0이어야 한다.
따라서 숫자 N을 입력받은 후 각 자리의 수가 3의 배수이며 0을 포함하는지 확인한다. 만약 둘 중 하나의 조건이라도 만족하지 않는다면 해당 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들 수 없으므로 -1을 출력한다.
만약 두 조건을 만족한다면 해당 숫자를 큰 수부터 나열한 수는 각 자릿수가 3의 배수이며 마지막 일의 자리가 0이기 때문에 30의 배수라는 조건을 만족하는 가장 큰 수가 된다.

---

변수 설명(솔루션과 코드)

K:  주어진 어떠한 수의 각 자릿수를 저장한 리스트

---

솔루션

K의 모든 원소(어떠한 수의 각 자릿수)의 합이 3의 배수인지, 그리고 K가 0을 포함하는지를 확인한다.

만약 두 가지 조건을 모두 만족한다면 K를 내림차순으로 정렬한 후 문자열 형태로 출력한다.

(배열을 그냥 출력하는 경우 [5, 4, 3, 2, 1]과 같은 형태로 출력되기 때문에 join 함수를 이용하여 문자열 형태로 출력해야 한다.)

* join: 입력된 문자열, 리스트, 튜플의 원소 사이에 특정 구분자를 포함하여 문자열로 변환하는 python의 내장 함수

"구분자".join(입력)과 같은 형태로 작성하는데 이때 문자열, 리스트, 튜플 등이 입력될 수 있다.

입력된 문자열, 리스트, 튜플의 각 원소 사이에 구분자를 넣어 하나의 문자열로 변환한다.

---

코드(Python)

K = (input())
K = [int(i) for i in K]
if (sum(K) % 3) == 0 and 0 in K:
    print("".join(map(str,sorted(K,reverse=True))))
else:
    print(-1)

 

설명에 잘못된 부분이 있거나 질문 사항이 있으시다면 언제든지 댓글 남겨주세요 :)