[백준(Baekjoon)][자바(java)] 10610 : 30 / 그리디

 

www.acmicpc.net/problem/10610

10610번: 30

 

문제 풀이

 

import java.io.*;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws IOException {
	
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		String n = br.readLine();
		br.close();
		
		int l = n.length(), s = 0, t, i;
		int a[] = new int[l];
		boolean isZeroExist = false;
		for( i = 0; i < l; i++ ) {
			t = n.charAt(i) - '0';
			if( t == 0 )  isZeroExist = true;
			a[i] = t;
			s += t;
		}
		
		String r;
		if( isZeroExist && ( s % 3 == 0 ) ) {
			StringBuilder sb = new StringBuilder();
			Arrays.sort( a );
			for( i = l-1; i >= 0; i-- ) 
				sb.append( a[i] );
			r = sb.toString();
		}
		else
			r = "-1";
		System.out.println( r );

	}
}

 

*  그리디

-  30의 배수 => 3의 배수이면서 1의 자리가 0인 수
   3의 배수 => 각 자리 숫자의 합이 3의 배수인 수
-  수를 String 타입으로 입력받고 숫자 하나하나 탐색하여 int[]배열에 넣고, 합을 구하고, 0이 있는지 판단
-  0이 존재하고 합이 3의 배수이면, int[] 배열을 정렬 후 큰 숫자부터 이어붙여 출력
   그렇지 않으면 30의 배수가 아니므로 -1 출력