문제
어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.
미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.
풀이
30의 배수판별법
- 0이 있는지 확인
- 0이 아닌 나머지숫자를 가지고 3의 배수를 만들수 있는지 확인하면 된다.
3의 배수 판별법
- 전체 자리수의 숫자합이 3의 배수 여야한다.
다른 배수 판별법을 보고싶으면 밑에 링크에서 확인할 수 있다.
이렇게 찾아진 숫자가 30의 배수라면 있는 숫자들을 내림차순로 정렬하면 가장 큰 수가 나온다.
하지만 문제는 입력에서 105자리수의 숫자를 입력한다. Integer 와 Long 모두 이를 담을 수 없기에 String 을 가지고 해야한다.
<코드>
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
public class Main {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String n = br.readLine();
int check = 0;
int i = 0;
List<Integer> num = new ArrayList<Integer>();
while( i < n.length()) {
check += Integer.parseInt(n.substring(i, i+1));
num.add(Integer.parseInt(n.substring(i, i+1)));
i++;
}
Collections.sort(num, Comparator.reverseOrder());
if(check % 3 == 0 && num.get(num.size()-1) == 0) {
for(int j : num) {
sb.append(j);
}
}
else {
sb.append(-1);
}
System.out.println(sb);
}
}
'알고리즘 공부 > 탐욕알고리즘(Greedy)' 카테고리의 다른 글
백준 2873 (롤러코스터) (0) | 2021.01.21 |
---|---|
백준 1931(회의실 배정) (0) | 2021.01.19 |
백준 1783(병든 나이트) (0) | 2021.01.18 |
백준 2875 ( 대회 or 인턴) (0) | 2021.01.17 |
백준 11047(동전 0) (0) | 2021.01.17 |