[Java] 백준 풀기 10610 - 30

자바 백준 10610번

실버 4

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

10610번: 30

 

 

 

 

 

문제 보기

분류: 수학, 그리디 알고리즘, 문자열, 정렬, 정수론

 

 

 

 

 

문제 풀기

30의 배수가 가능한지 알아보기 위해서 주어진 숫자의 각 자리를 모두 합한 값이 3의 배수가 되는지 확인하고 0이 하나라도 존재하는지 확인한다.

 

String 타입으로 입력 받은 숫자를 charAt() - '0' 방법을 이용하여 int 타입의 숫자로 변경한다.

0부터 9까지 각 숫자의 개수를 저장할 array에 각 카운트를 증가시켜 기록하고 모든 숫자를 누적합한다.

 

누적합한 값이 3의 배수가 되지 않거나 0의 개수를 담는 array에 0개가 기록되었으면 그 수는 30의 배수가 안되므로 "-1"을 반환한다.

 

30의 배수가 가능한 숫자 모음에 대해서는 가장 큰 숫자부터 꺼내고 StringBuilder의 append()를 사용하는 방식으로  가장 큰 수를 만든다. 만든 수를 toString() 하여 반환한다.

 

 

 

 

 

코드 보기

import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String N = sc.nextLine();  // 입력된 문자형 숫자
        
        String largestMultiple = findLargestMultiple(N);  // 함수를 호출하여 가장 큰 30의 배수를 찾음
        
        System.out.println(largestMultiple);  // 결과 출력
    }
    
    // 가장 큰 30의 배수를 찾는 함수
    public static String findLargestMultiple(String N) {
        int[] digitCount = new int[10];  // 각 숫자(0-9)의 개수를 저장할 배열
        int digitSum = 0;  // 모든 자릿수의 합을 저장할 변수
        
        // 각 자릿수를 하나씩 선택하여 확인
        for (int i = 0; i < N.length(); i++) {
            int digit = N.charAt(i) - '0';  // char 문자를 숫자로 변환하여 자릿수를 구함
            digitCount[digit]++;  // 해당 자릿수의 개수 증가
            digitSum += digit;  // 모든 자릿수의 합 계산
        }
        
        // 숫자의 총 합이 3의 배수가 아니거나, 0이 없는 경우 -1을 반환하여 결과가 없음을 표시
        if (digitSum % 3 != 0 || digitCount[0] == 0) {
            return "-1";
        }
        
        // 가장 큰 30의 배수를 저장할 문자열
        StringBuilder largestMultiple = new StringBuilder();
        
        // 큰 숫자부터 시작하여 가장 큰 30의 배수를 만듦
        for (int i = 9; i >= 0; i--) {
            while (digitCount[i] > 0) {
                largestMultiple.append(i);  // 해당 숫자를 결과 문자열에 추가
                digitCount[i]--;  // 사용한 숫자의 개수 감소
            }
        }
        
        // 결과 문자열 반환
        return largestMultiple.toString();
    }
    
}