백준 문제풀이

[Baekjoon 10610] 30 문제풀이 - JAVA

planting grass 2023. 2. 5. 15:58
728x90

[Silver IV] 30 - 10610

문제 링크

성능 요약

메모리: 32484 KB, 시간: 1088 ms

분류

그리디 알고리즘(greedy), 수학(math), 정수론(number_theory), 정렬(sorting), 문자열(string)

문제 설명

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력

미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

문제풀이

30의 배수는 아래와 같다.

30 60 90 120 150 180 210 240 270 300 330 360....

따라서 30의 배수가 되는 경우의 수는 아래와 같다.

  1. 맨 뒤에 0이 들어간다. (0의 개수는 최소 1개이며 여러개가 될 수 있다.)
  2. 각 자릿수들의 합이 3의 배수가 된다.

위 조건에 부합하면서 가장 큰 숫자를 구하려면 각 자릿수들을 큰 순서대로 정렬하면 된다.

숫자 80875542를 예시로 들자면 8 + 0 + 8 + 7 + 5 + 5 + 4 + 2 = 39

자릿수에 0이 한개 있으므로 1번 조건을 충족하고, 자릿수의 합이 39이므로 3의 배수이기 때문에 2번 조건도 충족한다.

여기서 가장 큰 수를 조합하면 88755420이 나오는데 이는 각 자릿수들을 따로 배열에 둔 다음 정렬을 돌리면 해결된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str = br.readLine();

        int arr[] = new int[str.length()];
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            arr[i] = str.charAt(i) - 48;
            count += arr[i];
        }

        Arrays.sort(arr);

        if ((count % 3 == 0) && (arr[0] == 0)) {
            for(int i = str.length() - 1; i > -1; i --) {
                System.out.print(arr[i]);
            }
        } else System.out.println(-1);

    }
}

코드 풀이

String str = br.readLine();

        int arr[] = new int[str.length()];
        int count = 0;
        for (int i = 0; i < str.length(); i++) {
            arr[i] = str.charAt(i) - 48;
            count += arr[i];
        }

String형 str에 입력을 넣는다.

int형 배열 arr을 str의 길이만큼 생성시킨 후, 각 자릿수의 합을 더해줄 int형 변수를 선언한다.

charAt를 사용해서 각 자릿수를 배열에 넣고, 동시에 count에 자릿수를 더해준다.

        if ((count % 3 == 0) && (arr[0] == 0)) {
            for(int i = str.length() - 1; i > -1; i --) {
                System.out.print(arr[i]);
            }
        } else System.out.println(-1);

각 자릿수의 합이 3으로 나눌때 나머지가 0이고, 정렬한 배열의 제일 작은 값이 0일 경우

str의 길이에서 1만큼 뺀값부터 0까지 배열의 값을 출력해준다.

만약 위 조건이 부합하지 않는다면 -1을 출력한다.

728x90