BOJ) 30 (자바, JAVA)

30

10610번: 30

풀이

 

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

문제에서 주어진 이 조건을 N의 최대값이 10^5로 읽어서 처음에는 DFS로 시도했다.

하지만, 최대 10^5개의 숫자니까 100000 개의 숫자로 이루어져 있다는 거니까 DFS는 어마어마한 요청이 들어가고 stack over flow가 뜬다..

 

런타임 에러가 뜨자마자 왜지?하고 봤더니 10^5가 숫자의 갯수였다.

그래서 로직을 찾아봤다.

 

30으로 나눠지는 숫자라는 조건이 이 문제의 해답이었다.

30을 소인수 분해하면, 2 * 3 * 5 라는 것을 알 수 있다.

이 조건에 의해, 만들어지는 숫자의 각 자리의 합은 3으로 나눠지는 숫자인 동시에, 10으로 나눴을 때 0이 나와야한다.

즉, 0이 적어도 한 번 이상은 들어가야한다는 소리다.

 

그래서 0~9까지 몇 번 들어왔는지 저장할 배열을 만들어줬다.

숫자의 각 자리를 돌면서, 해당 숫자의 갯수를 카운트했다.

또한, 각 자리의 숫자를 더하면서 3으로 나눈 나머지 값을 저장해줬다.

 

위의 과정을 마치고나서, 0이 1번 이상 들어가있는지, 모든 자리를 더한 값이 3으로 나누어 떨어지는지 확인하고

가능하다면 가장 큰 수를 만들고, 불가능하다면 -1을 출력해주었다.

 

가장 큰 수는 9~0까지 내림차순으로 모든 수를 적어내려가면 된다.

63990라는 숫자가 주어진다면, 이 숫자로 문제의 조건에 따라 만들 수 있는 최대 값은 99630이 된다.

 

 

 

런타임 에러 코드

 

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

public class Main {
    final static char ZERO = '0';
    private static long answer, THIRTY = 30;

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

        solution(numStr);
    }

    private static void solution(String numStr) {
        answer = -1;
        dfs(numStr, new boolean[numStr.length()], new LinkedList<>());
        System.out.println(answer);
    }

    private static void dfs(String numStr, boolean[] visit, LinkedList<Character> ansList) {
        if(ansList.size() == numStr.length()) {
            StringBuffer sb = new StringBuffer();
            for(char ch : ansList) {
                sb.append(ch);
            }
            long num = Long.parseLong(sb.toString());
            if(num %THIRTY ==0) {
                answer = Math.max(answer, num);
            }
            return;
        }

        for(int i=0; i<numStr.length(); i++) {
            if(!visit[i]) {
                visit[i] = true;
                char ch = numStr.charAt(i);
                if(ch == ZERO) {
                    if(!ansList.isEmpty()) {
                        ansList.offer(ch);
                        dfs(numStr, visit, ansList);
                        ansList.pollLast();
                    }
                } else {
                    ansList.offer(ch);
                    dfs(numStr, visit, ansList);
                    ansList.pollLast();
                }
                visit[i] = false;
            }
        }
    }
}

 

 

성공 코드

 

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

public class Main {
    final static char ZERO = '0';
    final static String FAIL = "-1";
    private static int THIRTY = 30, MAX_VALUE = 9, DIV = 3;

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

        solution(numStr);
    }

    private static void solution(String numStr) {
        int[] numArr = new int[MAX_VALUE+1];
        int sum = 0;
        for(int i=0; i<numStr.length(); i++) {
            int num = numStr.charAt(i)-ZERO;
            numArr[num]++;
            sum = (sum+num)%DIV;
        }
        if(numArr[0] == 0 || sum != 0) {
            System.out.println(FAIL);
        } else {
            StringBuffer sb = new StringBuffer();
            for(int i=MAX_VALUE; i>=0; i--) {
                for(int j=0; j<numArr[i]; j++) {
                    sb.append(i);
                }
            }
            System.out.println(sb.toString());
        }
    }
}