[백준 - 1039번] 교환 - Java

문제 링크

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

문제

티어: 골드 2
알고리즘: 그래프, dfs

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

풀이

연산이 K번 주어졌을 때 만들 수 있는 가장 큰 수를 출력해야 한다.

스왑할 두 위치를 뽑아서 K번 진행한다면, 6C2^K이기 때문에 불가능하다. 그런데 생각해 보면, 스왑을 하다가 같은 값이 올 수 있다는 것을 알 수 있다.

그렇기 때문에 이러한 중복을 줄인다면, 전체 경우의 수가 몇일까?라는 생각이 든다.

그래서 계산해 보면, 전체 경우의 수는 N이 100만보다 작거나 같은 자연수이기 때문에 100만 x K가 된다.

그러면 최대 1000만이기 때문에 충분히 가능한 수이고, visited 처리를 해서 중복 탐색을 방지할 수 있다.

나는 이를 dfs로 구현했다. dfs에서는 현재 수에서 스왑할 수 있는 모든 두 위치를 스왑 후 다음 깊이로 넘어간다. 그리고 현재 수와 K 횟수를 통해서 중복 탐색인지 아닌지를 판단하고, 진행했다.

이 풀이의 정확한 시간 복잡도는 O((N최대 자릿수!) * K)가 된다.

예를 들어 16375같은 경우는 첫 번째 자리에 6가지 수가 올 수 있고, 다음 자리에는 5가지, 4가지..해서 6! * K가 된다.

소스 코드

import java.io.*;
import java.util.*;

public class Main {
    static int answer = -1;
    static int N, K, maxDigit;
    static boolean[][] visited;
  public static void main(String args[]) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      N = Integer.parseInt(st.nextToken());
      K = Integer.parseInt(st.nextToken());
      maxDigit = getIntLength(N);
      visited = new boolean[1000001][K + 1];
      dfs(N, 0);
      
      System.out.println(answer);
  }
  
  static void dfs(int number, int depth) {
      if(visited[number][depth]) {
          return;
      }
      
      if(getIntLength(number) != maxDigit) {
          //첫 번째가 0이 됐음을 의미
          return;
      }
      
      if(depth == K) {
          answer = Math.max(answer, number);
          return;
      }
      
      visited[number][depth] = true;
      
      for(int i=1; i<=maxDigit - 1; i++) {
          for(int j=i + 1; j<=maxDigit; j++) {
              //i와 j를 스왑
              int iD = getDigitByMath(number, i);
              int jD = getDigitByMath(number, j);
              
              int subValue = (int) Math.pow(10, i - 1) * iD + (int) Math.pow(10, j - 1) * jD;
              int addValue = (int) Math.pow(10, j - 1) * iD + (int) Math.pow(10, i - 1) * jD;
              
              int newNumber = (number - subValue) + addValue;
              
              dfs(newNumber, depth + 1);
          }
      }
  }
  
  static int getDigitByMath(int number, int position) {
      //포지션은 오른쪽부터 1임.
      if(getIntLength(number) < position) {
          return -1;
      }
      return (number / (int) Math.pow(10, position - 1)) % 10;
  }
  
  static int getIntLength(int number) {
      return (int) (Math.log10(number) + 1);
  }
}