인프런 가장 가까운 큰수

문제

나의 풀이

import java.util.ArrayList;

public class NearestNum {
    static int answer, target, m;
    static ArrayList<Integer> nums;
    static int[] check;
    static boolean flag;
    public static void DFS(int L, int number) { // L : 레벨, number : 만들어지는 숫자
        if(flag) { // 이미 가장 가까운 큰수를 찾은 경우
            return;
        }
        if(L == m) { // 모든 요소를 사용하여 숫자가 다 만들어졌을 때
            if(number > target) { // 주어진 n보다 클 때(가장 작은 n보다 큰수인 상태)
                answer = number; // 정답을 number로
                flag = true; // 가장 가까운 큰수를 만들 수 있음을 표시해줌
            }
        } else {
            for(int i = 0; i < m; i++) { // 순열 코드
                if(check[i] == 0) { // 사용하지 않은 요소인 경우
                    check[i] = 1; // 사용한다고 표시
                    DFS(L + 1, number * 10 + nums.get(i)); // 레벨 1 증가, 요소 사용한 숫자 만들어서 재귀 호출
                    check[i] = 0; // 백트래킹
                }
            }
        }
    }
    public static int solution(int n) {
        answer = 0;
        flag = false;
        nums = new ArrayList<>();
        target = n;
        int tmp = n;
        while(tmp > 0) { // n을 각 자리수로 분리
            int t = tmp % 10;
            nums.add(t); // nums에 각 자리수 추가
            tmp = tmp / 10;
        }
        nums.sort((a, b) -> a - b); // DFS 순열에 의해서 숫자가 만들어지는 순서가 오름차순으로 나타나게 하기 위해
        m = nums.size();
        check = new int[m]; // 사용했는지 안했는지 여부
        DFS(0, 0); // DFS 호출
        if(flag == false) {
            return -1;
        }
        return answer;
    }

    public static void main(String[] args) {
        System.out.println(NearestNum.solution(123));
        System.out.println(NearestNum.solution(321));
        System.out.println(NearestNum.solution(20573));
        System.out.println(NearestNum.solution(27711));
        System.out.println(NearestNum.solution(54312));
    }
}

dfs 순열 문제다.
n을 한자리씩 분리해서 배열 nums를 만들고 이를 오름차순 정렬한다.
그런 다음 DFS(0, 0)을 호출한다. DFS의 첫번째 매개변수는 레벨을 나타내고 두번째 매개변수는 만들어지는 숫자 number를 나타낸다. 함수 내부에서 nums에 있는 원소를 for문을 이용하여 하나씩 택하면서(check 배열에 사용했음을 표시) 숫자를 만들며 뻗어나간다. 십진수 숫자 number를 만들 땐 number * 10 + nums[i] 식을 이용하면 된다. 레벨이 n의 길이가 됐을 때 숫자가 완성됐다는 뜻이고 n보다 크면 바로 정답이 된다. 오름차순으로 완성되기 때문에 가장 작은 수는 처음 발견한 수이기 때문이다.

결과