1 분 소요

[공지사항] 알고리즘 카테고리 포스트 살펴보기

:rocket: 문제 설명

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

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

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

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



:rocket: 문제 풀이

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));

        String numberLine = br.readLine();
        Integer numArr[] = new Integer[numberLine.length()];

        // 풀이
        boolean zeroExists = false;
        int totalSum = 0;
        for (int i = 0; i < numberLine.length(); i++){
            numArr[i] = numberLine.charAt(i) - '0';
            if (numArr[i] == 0) zeroExists = true;
            totalSum += numArr[i];
        }

        if (!zeroExists) {
            bw.write("-1");
            bw.flush();
            return;
        }
        if (totalSum % 3 != 0 || totalSum == 0){
            bw.write("-1");
            bw.flush();
            return;
        }

        StringBuilder sb = new StringBuilder();

        Arrays.sort(numArr, Collections.reverseOrder());

        for (int i = 0; i < numArr.length; i++){
            bw.write(Integer.toString(numArr[i]));
        }
        bw.flush();
    }

}

문제 풀이는 다음과 같은 방식으로 구성했다.

String의 형태로 입력받고,
한자리씩 Integer 배열로 변환한 뒤, 내림차순 정렬할 것.
검증한 후 정렬된 Integer 배열을 출력할 것.

위 풀이는 30의 배수가 되기 위해서는 반드시 0이 포함되어있어야 하며, 모든 자릿수를 더했을 때 3의 배수가 되어야 한다는 점을 반영했다.

그러기 위해서 0이 포함되어 있는지 확인하기 위해 zeroExists 변수와

더했을 때 3의 배수가 되는지 확인하기 위해 totalSum 변수를 썼다. (물론 여기서 단순히 0만 입력되는 경우를 피하기 위해 조건식을 추가했다.)

그렇게 검증이 되었다면 자리만 바꿔서 가장 큰 수를 만들어주면 된다.

당연히 그냥 큰 수부터 먼저 출력하면 되니깐 그냥 내림차순 정렬한 순으로 출력했다.

참고