[알고리즘] 16943번

오늘 풀어볼 문제는 백준 16943번 문제 "숫자 재배치" 이다.

이 문제는 실버1 문제이고 브루트 포스 문제이다.

문제

두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 

가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0으로 시작하면 안 된다.

입력

첫째 줄에 두 정수 A와 B가 주어진다.

출력

B보다 작은 C중에서 가장 큰 값을 출력한다. 그러한 C가 없는 경우에는 -1을 출력한다.

📌첫 번째 시도📌

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    static String A;
    static int B;
    static int[] array;
    static boolean[] visited;
    static int max;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        A = st.nextToken();
        B = Integer.parseInt(st.nextToken());
        array = new int[A.length()];
        visited = new boolean[A.length()];

        for(int i=0; i<array.length; i++) {
            array[i] = A.charAt(i) - '0';
        }

        Arrays.sort(array);
        max = -1;

        cal(0, 0, visited);

        System.out.println(max);
    }
    private static void cal(int nowNumber, int count, boolean[] visited) {
        if(count == A.length()) {
            if(max < nowNumber) {
                max = nowNumber;
            }
            return;
        }
        for (int i = 0; i < A.length(); i++) {
            if (visited[i] || (array[i] == 0 && count == 0))
                continue;
            if (nowNumber * 10 + array[i] > B)
                continue;
            visited[i] = true;
            cal(nowNumber * 10 + array[i], count + 1, visited);
            visited[i] = false;
        }
    }
}

아직 재귀 호출 함수를 짜는 데 익숙하지 않은 것 같다. 그래도 이번 문제는 잘 풀린 것 같다.
하지만 살짝의 문제를 더하자면 BufferedWriter를 만들어 놓고 쓰질 않았다.. ㅎㅎ

그래서 사용해서 성능을 업 해보겠다.

으엑??? BufferWriter를 쓴다고 해서 시간이 줄어드는 게 아닌가보다..?

이 이유에 대해서 좀 알아볼 필요가 있을 것 같다..

[문제 출처] https://www.acmicpc.net/problem/16943