[Silver4-JAVA] 백준 10610 - 30

10610번: 30

 

 

🤔 문제 접근

처음에는 양수 N을 문자열로 받은 뒤 백트래킹을 통해 숫자들의 위치를 바꿔가며 30의 배수를 찾고자 했다.

하지만 숫자들을 몇번 바꾸어줘야할지에 대한 상한선을 설정하는 것이 힘들었고 숫자의 길이가 길어지면

길어질 수록 시간 복잡도가 증가하는 문제가 있었다.

 

해당 문제를 풀기 위해서는 수학적 지식이 조금 필요한 것 같다.

 

먼저 30의 배수가 되기 위해서는 주어진 양수 N에 반드시 0이 1개 이상 존재해야한다.

또한 30의 배수인 30, 60, 90, 120, 150, 180, 210 ... 의 공통점을 존재하는데

바로 각 자릿수의 합이 3의 배수인 것이다. 

 

따라서 위 두가지 방법을 이용해 30의 배수인지 아닌지 파악할 수 있으며

만약 조건을 만족한다면, 해당 숫자가 존재한다는 가정하에 9부터 0까지 모든 수들을

버퍼에 담아 출력하면 된다.

 

🚨CODE

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		// 숫자를 섞었을 때 30의 배수가 등장하는 수는
		// 0을 포함하고있으며 모든 자릿수를 더했을 때 3의 배수가 되는 수다.
		String[] str = br.readLine().split("");
		int[] num = new int[10];
		int sum = 0;
		for(int i = 0; i<str.length; i++) {
			int n = Integer.parseInt(str[i]);
			num[n]++;
			sum+=n;
		}
		
		if(num[0] == 0 || sum%3 != 0) {
			System.out.println(-1);
			return;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i = 9; i>=0; i--) {
			while(num[i] > 0) {
				sb.append(i);
				num[i]--;
			}
		}
		
		System.out.println(sb.toString());
	}
}