boj14629 숫자 조각 _ java

링크

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;
              }
          }
      }
  }

결과