[BFS] 백준-10610 30 실버4

백준-10610 : 30

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

10610번: 30

 

아이디어

• 30의 배수 3의 배수이면서 10의 배수
  • 3의 배수 조건 : 각자리 합이 3의배수
  • 10의배수 조건 1의 자리의 숫자가 0

 

풀의

• 숫자를 입력받은 후 각자리 합을 더하면서 우선순위 큐에 넣는다.
• 우선순위 큐에서 꺼낸면서 결과에 더한 후 1의 자리가 0인지 확인한다.

코드 (java)

package Bfs.Baejoon2437;

import java.util.*;

public class Baejoon2437 {

    public static void main(String[] args) {

        String result = "";
        Scanner sc = new Scanner(System.in);
        String num = sc.nextLine();
        int sum = 0;

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        for (int i = 0; i < num.length(); i++) {
            int tempNum = num.charAt(i) - '0';
            pq.add(tempNum);
            sum = (sum + tempNum) % 3;
        }

        if (sum % 3 != 0) {
            System.out.println(-1);
        } else {
            while (!pq.isEmpty()) {
                result = pq.poll() + result;
            }

            if (result.charAt(result.length() - 1) == '0') {
                System.out.println(result);
            } else {
                System.out.println(-1);
            }
        }
    }
}