백준 10610 30 Java

그리디 알고리즘 문제인 30이다.

 

문제를 이해하지 못해서 풀지 못했는데

주어진 수들을 아무렇게나 조합해서 가장 큰 30의 배수를 찾는 문제인줄 알았다.

310이 주어졌으면 가장 큰수인 310은 30의 배수가아니므로 아니고

310을 가지고 30을 만들 수 있으므로 답을 30으로 출력되도록 문제를 풀어나갔다.

 

그런데 문제는 그런게 아니라 주어진 수를 전부 사용해야만 했다.

 

그래서 주어진 수를 한자리씩 빼서 일단 정렬한 다음에 역순으로 출력해

가장 큰 수를 만든후 그 수가 30의 배수인지 체크하여 문제를 풀고 제출했다.

 

하지만 이런식으로 풀면 어김없이 시간초과가 발생했다.

더 빠르게 해본다고 여러가지의 방법을 시도했지만 3연속 시간초과의 시련을 만나게된다.

 

정답인 풀이법은 이러했다.

30을 소인수분해 해보면 2,3,5가 나오게 된다. 이를 통해 알 수 있는건

첫 번째로 2*5 = 10이므로 2의배수와 5의배수에 모두 해당되려면 무조건 0으로 끝나야 한다.

두 번째로 값은 3의 배수의 특징으로 모든 자리수에 있는 수를 합한게 3의 배수여야 한다.

 

1. 값이 0으로 끝나야한다.

2. 모든 자리 수에 있는 값의 합이 3의 배수여야 한다.

 

이 두가지조건을 이용해 코드를 최대한 시간을 아끼게 짜면 정답이 된다.

코드를 통해 살펴보자..

코드보다 for문이 한개라도 더있으면 시간초과가 나오더라..

 

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String s = scan.next();
        List<Integer> list = new ArrayList<>();
        int sum = 0;
        
        for(int i=0; i<s.length(); i++) {
            sum += s.charAt(i)-'0';
            list.add(s.charAt(i)-'0');
        }
        
        Collections.sort(list);
        if(list.get(0)==0 && sum %3 == 0) {//30의 배수가 맞으면
            for(int i=list.size()-1; i>=0; i--)//출력
                System.out.print(list.get(i));
        }
        else
            System.out.println(-1);
   }