10610

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

 

그리디 문제...

 

순열과 이것 저것 시도해보다 자리수가 10^5인 것을 보고 String으로 선회했다.

배수판정법 위키를 찾아보니.. 

 

https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95

 

30의 배수 판정법은 두가지 조건을 만족한다.

 

1. 각자리수의 합이 3의 배수일 것

2. 0으로 끝날 것

 

위 조건만 알면 코딩은 별게 없다.

0을 뒤로 빼거나 다른 걸 생각할 필요없이 내림차순 정렬한 값이 최대값이 된다.

 

그리디란... 참 알면 별거 아닌것 같고, 코드는 효율적인데 처음 봤을 땐 직관적이지 않아서 나랑은 잘 안맞는 것 같다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
import java.util.*;

public class Main {

	static int N;
	static boolean DBG = false;
	static boolean[] visited;
	static Integer[] arr;
	static String answer = "-1";

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		String s = st.nextToken();		
		arr = new Integer[s.length()];
		
		int sum =0;
		int idx= s.length()-1;
		for (char c : s.toCharArray()) {
			arr[idx] = c-'0' ;
			sum += arr[idx];
			idx--;
		}
		
		if ( sum % 3 ==0 && s.lastIndexOf('0') !=-1 ) {
			Arrays.sort(arr, Collections.reverseOrder());
			StringBuilder sb =new StringBuilder();
			for ( int v : arr)
				sb.append(v);
			
			answer = sb.toString();
		} else {
			System.out.println(answer);			
		}
	
	}

}