30(10610번)

• 티어 : Sliver 4
• 정답여부 : 오답
• 알고리즘 유형 : 수학, 그리디 알고리즘, 문자열, 정렬
• 시간 제한 : 1초

💡문제

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

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

💡입력

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

💡출력

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

💡예제 입력 1

30

💡예제 출력 1

30

💡예제 입력 2

102

💡예제 출력 2

210

💡예제 입력 3

2931

💡예제 출력 3

-1

💡예제 입력 4

80875542

💡예제 출력 4

88755420

💡문제요약

각 자리 숫자를 재배치하여 만들 수 있는 가장 큰 숫자 중 30의 배수가 되는 가장 큰 숫자를 만들면 되는 문제

💡알고리즘 설계

1. 새로 만들 수는 30의 배수임으로 즉 10의 배수이며 동시에 3의 배수여야 한다. 따라서 10의 배수이니 끝자리는 무조건 0이고 모든 자리수의 합은 3의 배수여야한다.
2. 입력값을 char 배열로 받고 정렬한다.
3. 끝부터 반복문을 돌면서 문자열 - '0' 값을 sum에 더한다. 동시에 StringBuilder에 문자열을 추가한다.
4. sum이 3의 배수가 아니거나 input[0]이 '0'이 아니라면 30의 배수를 만들 수 없다. -1을 출력하고 종료한다.
5. 4에서 끝나지 않았다면 StringBuilder를 출력한다.

💡작성코드

• Java

package algorithms_Java03_06;
import java.io.*;
import java.util.*;
public class baekjoon_10610 {
	public static void main(String[] args) throws IOException{
		char[] input = new BufferedReader(new InputStreamReader(System.in)).readLine().toCharArray();
	      int sum = 0;
	      Arrays.sort(input);
	      StringBuilder sb = new StringBuilder();
	      for(int i=input.length-1;i>=0;i--){
	         sum +=input[i]-'0';
	         sb.append(input[i]);
	      }	 
	      //3의 배수,10의 배수 가능성 체크
	      if(sum%3!=0 || input[0]!='0'){
	         System.out.println(-1);
	         return;
	      }	 
	      System.out.println(sb);
	   }
	}

💡시간복잡도

O(n log n)

💡틀린 이유 or 수정할 부분

처음 문제가 이해가 안 가서 코드를 작성하는데 시간이 오래 걸린거 같다. 그래서 구글링을 통해 문제를 이해 했다..

좀 더 이해하기 쉬운 코드를 가져와봤다.

💡틀린 부분 수정 or 다른풀이

• Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String N = br.readLine();
        ArrayList<Integer> list = new ArrayList<>();
        for(int i=0; i<N.length(); i++)
        {
            list.add(N.charAt(i) - '0');
        }
        if(list.contains(0) == false)
        {
            System.out.println(-1);
            return;
        }
        int sum = 0;
        for(int i=0; i<N.length(); i++)
        {
            sum = sum + list.get(i);
        }
        if(sum % 3 != 0 || sum == 0)
        {
            System.out.println(-1);
            return;
        }
        else
        {
            list.sort(Comparator.reverseOrder());
        }
        for(int i=0; i<N.length(); i++)
        {
            System.out.print(list.get(i));
        }
    }
}

💡느낀점 or 기억할 정보

문제를 보면 무엇을 구현해야할지 찾아야 할지 딱 답이 나와야 알고리즘을 설계하는데 문제가 없는데 그게 힘들다 ㅠㅠ