백준 16943번 : 숫자 재배치(Java)

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

16943번: 숫자 재배치

---

[풀이]

• dfs를 이용한 브루트포스형의 문제입니다.
• 처음 입력 받는 값은 숫자를 재배치 해야하므로, 값을 하나씩 저장하기 위해 배열로 선언, 비교가 되는 변수 b는 정수형으로 선언합니다.
• 출력해야하는 answer 변수는 -1로 초기화합니다.
• dfs를 구현할 때 배열의 해당 인덱스를 사용했는지 파악하기 위해 visited라는 boolean형의 배열 변수를 선언했습니다.
• dfs를 구현할 때 조건은 두가지가 있습니다.
  • b 변수보다 크면 안됩니다.
  • 위치가 재배치된 경우의 수는 0으로 시작하면 안됩니다.

---

[코드]

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int answer, b;
    static int[] a;
    static String input;

    public static void solve(int nowNumber, int count, int len, boolean[] visited) {
        if (count == input.length()) {
            answer = Math.max(answer, nowNumber);
            return;
        }
        for (int i = 0; i < input.length(); i++) {
            if (visited[i] || (a[i] == 0 && count == 0))
                continue;
            if (nowNumber * 10 + a[i] > b)
                continue;
            visited[i] = true;
            solve(nowNumber * 10 + a[i], count + 1, input.length(), visited);
            visited[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        input = st.nextToken();
        a = new int[input.length()];
        b = Integer.parseInt(st.nextToken());
        answer = -1;
        boolean[] visited = new boolean[input.length()];
        for (int i = 0; i < input.length(); i++) {
            a[i] = input.charAt(i) - '0';
        }
        solve(0, 0, input.length(), visited);

        System.out.println(answer);
    }
}