boj14629 숫자 조각 _ java

dgh03207·2022년 5월 14일
0

알고리즘

목록 보기
36/45

링크

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

문제

곧 7살을 맞이하는 준하는 유치원에서 숫자가 적힌 나무 조각들을 가지고 노는 것을 좋아한다. 숫자 조각은 총 10개이며, 각각의 조각엔 0부터 9까지의 숫자가 한 숫자씩 적혀있다. 준하는 각 숫자 조각을 이어 붙이면 더 큰 숫자를 만들 수 있고, 정말 다양한 조합이 존재한다는 점이 마음에 무척 들었다. 오늘도 준하는 숫자 조각으로 만들 수 있는 가장 큰 숫자인 9876543210을 보면서 흥분을 감추지 못하고 있었다. 그러나 그런 준하를 보다 못 한 강민이는 준하에게 딴지를 걸기 시작했다.

“그거 가지고는 333도 못 만들지? 깔깔깔”

강민이의 도발에 화가 난 준하는 숫자 조각을 빠르게 조합한 후, 강민이에게 대답했다.

“333은 못 만들어도 329를 만들면 별로 차이 안 나!”

그 말을 들은 강민이는 어이가 없었지만 준하를 놀려먹기로 하고 다음과 같이 말했다.

“그래? 그럼 44223344는?”

순간 준하는 머리가 멍해지며 아무런 생각이 들지 않았다. 이대로 가면 준하는 미래에 수포자가 될 것이다. 준하가 수학을 포기하지 않도록 대신 계산해주는 프로그램을 만들어주자.

입력

첫째 줄에 강민이가 질문하는 숫자 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)

출력

첫째 줄에 0부터 9까지의 숫자를 한 번만 사용하여 만든 숫자 중에 N과 가장 차이가 적은 숫자를 출력한다. 답이 여러 개일 경우, 더 작은 숫자를 출력한다.

나의 풀이

  • 이 문제는 평범한 백트래킹 문제이지만, 예외 처리 부분이 까다로웠다. 또, 입력 값이 워낙 크기 때문에, 나는 String 으로 처리하였다.

  • 입력 숫자값을 String 으로 받아

    • 문자열의 길이를 세서 10이하이거나,

    • 숫자가 9876543210(숫자카드로 만들 수 있는 경우중 가장 큰 수)보다 큰

      경우는, 숫자카드를 뽑아 만들 수 있으므로, 백트래킹 을 진행하여 원하는 작업을 진행한다. 그외의 답은 모두 9876543210 이 답이다.

  • 입력 숫자값의 길이가 digit 이라고 하자. 백트래킹은 3가지 경우를 모두 고려해야한다.

    • 길이가 digit 인 숫자
    • 길이가 digit-1 인 숫자
      • 단, digit-1 인 경우 입력 숫자의 자릿수가 1 이면 0 의 자릿수는 없기때문에, digit이 1이 아닐때 의 조건이 들어가야한다.
    • 길이가 digit+1 인 숫자
      • 단, digit+1 인 경우 입력 숫자의 자릿수가 10 이면 11 의 자릿수는 만들 수 없기 때문에, digit이 10이 아닐때 의 조건이 들어가야 한다.
  • 해당 풀이는 스터디의 @이건 님의 도움을 받았다.

  • 전체 코드

    package Baekjoon.java.silver;
    
    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.math.BigInteger;
    
    public class boj14629 {
        static String Num,answer;
        static Long minResult,targetNum;
        public static void main(String[] args) throws Exception{
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            minResult = 9876543210L;
            Num = br.readLine();
            targetNum = Long.parseLong(Num);
            if(targetNum>=minResult){
                System.out.println("9876543210");
            }else if(Num.length()<=10){
                boolean[] numbers = new boolean[10];
                int digit = Num.length();
                dfs(numbers,0,"",digit);
                if(digit!=1){
                    dfs(numbers,0,"",digit-1);
                }
                if(digit!=10){
                    dfs(numbers,0,"",digit+1);
                }
    
                System.out.println(Long.parseLong(answer));
            }
        }
    
        private static void dfs(boolean[] numbers,int idx,String myNum,int Max){
            if(idx==Max){
                Long calNum = Long.parseLong(myNum);
                Long result = Math.abs(calNum-targetNum);
                if(minResult>result){
                    minResult = result;
                    answer = myNum;
                }
                return;
            }
    
            for (int i = 0; i <10; i++) {
                if(!numbers[i]){
                    numbers[i] = true;
                    dfs(numbers,idx+1,myNum+Integer.toString(i),Max);
                    numbers[i] = false;
                }
            }
        }
    }

결과

profile
같이 공부하자!

0개의 댓글