[백준] 10610번: 30(그리디)

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

10610번: 30

 

코드

import java.util.Scanner;

public class Main {
	public static String str;
	public static int[] numCountArr;

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		str = scan.next();			// 입력받은 N
		numCountArr = new int[10];	// 입력받은 문자열의 각 자릿수를 저장
		long total = 0;
		for(int i=0; i<str.length(); i++) {
			// 문자열의 각 자릿수 저장
			int strNum = Integer.parseInt(str.substring(i, i+1));
			numCountArr[strNum] ++;
			total += strNum;
		}

		// 입력받은 문자에 0이 없거나, 각 자릿수의 합이 3의배수가 아니면 30의배수가 아님.
		if(!str.contains("0") || total%3 != 0) {
			System.out.println("-1");
			return;
		}
		
		StringBuilder sb = new StringBuilder();
		for(int i=9; i>=0; i--) {	// 큰수부터 저장
			while(numCountArr[i] > 0) {
				sb.append(i);
				numCountArr[i] --;
			}
		}
		System.out.println(sb.toString());
		
		scan.close();
	}

}

 

풀이

어렵다... 다른 글들을 참고해서 풀었다.

30의 배수가 되는 조건을 찾아야한다 !!

 

30의 배수는 30, 60, 90, 120, 150, 180, 210, 240, 3000, 3030, 3060, ...

- 끝에 무조건 0으로 끝나야한다.

- 또한 각 자릿수의 합이 3의 배수이다.

 

또한 주의할점은 N이 10^5개의 숫자로 되어있다 -> 100000 까지가 아닌 100000 자릿수이다.

따라서 int나 long로 해결할 수 없고 문자열로 입력받아야 한다.

 

먼저 for문을 통해 주어진 문자열의 각 자릿수를 인덱스로 가지는 배열에 저장하고,(numCountArr[])

각 자릿수의 합을 더해준다.(total)

		for(int i=0; i<str.length(); i++) {
			// 문자열의 각 자릿수 저장
			int strNum = Integer.parseInt(str.substring(i, i+1));
			numCountArr[strNum] ++;
			total += strNum;
		}

 

 

위 for문이 끝나면 입력받은 문자에 0이 없거나, 3의 배수가 아닌지 판단한다.

-> 0이 없거나 3의 배수가 아니면 30의 배수가 아니므로 -1을 출력하고 종료한다.

		// 입력받은 문자에 0이 없거나, 각 자릿수의 합이 3의배수가 아니면 30의배수가 아님.
		if(!str.contains("0") || total%3 != 0) {
			System.out.println("-1");
			return;
		}

 

 

만약 위 조건을통해 0이 있고 3의배수일경우 => 주어진 문자열은 30의 배수이다.

따라서 가장 큰 수를 출력해준다.

		StringBuilder sb = new StringBuilder();
		for(int i=9; i>=0; i--) {	// 큰수부터 저장
			while(numCountArr[i] > 0) {
				sb.append(i);
				numCountArr[i] --;
			}
		}
		System.out.println(sb.toString());