[알고리즘-자바] 백준 10610번 30

문제

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

10610번: 30

언어

자바 JAVA

로직

입력

30의 배수인 가장 큰 값을 찾아야 하므로 int 타입의 배열에 값을 저장하고 내림차순 정렬을 해줍니다.

String input = br.readLine();

Integer[] arr = new Integer[input.length()];
for (int i = 0; i < arr.length; i++) {
    arr[i] = input.charAt(i) - '0';
}

Arrays.sort(arr, Comparator.reverseOrder());

 

30의 배수가 아닐 때

값이 30의 배수이기 위해서는 일의 자리가 0이면서 30으로 나누어지는 수이어야 합니다. 일단 입력받은 수의 일의 자리 값이 0이 아닌지 확인합니다.

위에서 오름차순으로 정렬을 했기 때문에 배열의 가장 마지막에 저장된 값이 일의자리 수입니다.

// 일의 자리가 0이 아닐 때
if (arr[arr.length - 1] != 0) { 
    System.out.println(-1);
}
// 일의 자리가 0일 때
else {
	생략...
}

30의 배수일 때

배열에 저장된 값을 다시 문자열로 저장해 줍니다. 이때 StringBuffer를 사용한 이유는 String은 immutable한 변수이기 때문에 덧셈을 할 때마다 String타입의 변수가 새로 생성되기 때문에 메모리를 잡아먹기 때문입니다.

StringBuffer sb = new StringBuffer();
for (int num : arr) {
    sb.append(num);
}

BigInteger num = new BigInteger(sb.toString());

근데 갑자기 BigInteger 타입의 변수가 나왔는데, 문제에서 10의 5승까지 값을 받을 수 있다고 나와있습니다. long 타입의 경우 19자리까지 저장할 수 있기 때문에 10의 5승 값을 저장할 수 없습니다. 이 때 BigInteger 타입을 사용하는데, 자세한 건 여기를 참고해 주세요.

 

이제 num 값과 30을 나누어 나머지가 존재하는지 판단해야 합니다. BigInteger 타입의 경우 compareTo 메서드로 값을 비교할 수 있습니다. 

• 0 : 두 값이 같다
• 1 : 왼쪽이 더 크다
• -1 : 오른쪽이 더 크다

int result = num.mod(BigInteger.valueOf(30L)).compareTo(BigInteger.valueOf(0L));
if (result == 0) {
    System.out.println(sb);
} else {
    System.out.println(-1);
}

---

최종 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Comparator;

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String input = br.readLine();

        Integer[] arr = new Integer[input.length()];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = input.charAt(i) - '0';
        }

        Arrays.sort(arr, Comparator.reverseOrder());

        if (arr[arr.length - 1] != 0) {
            System.out.println(-1);
        } else {
            StringBuffer sb = new StringBuffer();
            for (int num : arr) {
                sb.append(num);
            }

            BigInteger num = new BigInteger(sb.toString());
            int result = num.mod(BigInteger.valueOf(30L)).compareTo(BigInteger.valueOf(0L));
            if (result == 0) {
                System.out.println(sb);
            } else {
                System.out.println(-1);
            }
        }
    }
}