[DFS] 중복 순열 - 시간 초과 코드 수정

DFS 중복순열을 만드는 알고리즘이였는데

만들어진 배열 원소의 합이 주어진 특정 수와 똑같을 때 그 배열의 최소 사이즈를 구하는 것이였다.

 

import java.util.Scanner;

public class Main {
    static int n, m;
    //제일 큰수로 해야됨 ( 최소 개수를 구하는 것이기 때문에 )
    static int answer = Integer.MAX_VALUE;
    static int[] arr;

    //L-동전 갯수
    public void DFS(int L, int sum) {
        if (sum > m) return;
        if (sum == m) {
            answer = Math.min(L, answer);
        } else {
            for (int i = 0; i < n; i++) {
                DFS(L + 1, sum + arr[i]);
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner fb = new Scanner(System.in);
        n = fb.nextInt();
        arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = fb.nextInt();
        }
        m = fb.nextInt();
        T.DFS(0, 0);
        System.out.println(answer);
    }
}

시간 초과가 떴다 !

원인은 배열의 작은 수부터 돌기 때문에 만들어지는 순열이 너무 많기 때문이라고..

예를 들어 더하여 만들어야되는 숫자가 15인데 사용할 수 있는 숫자 중에 1이 있어 1부터 하게 되면 순열 사이즈가 15까지 가게된다 

 

해결 방법

사용할 수 있는 숫자 배열을 내림차순 정렬하여 큰 수부터 사용해서 순열을 만들면 만들 수 있는 제일 작은 순열부터 나올 것이다

그래서 사용 가능한 숫자 배열을 내림차순 정렬해주고 중복순열을 구할 때 이미 나온 가장 작은 순열 사이즈보다 더 큰 사이즈가 나오면 return하는 코드도 넣어줬다.

public class Main {
    static int n, m;
    //제일 큰수로 해야됨 ( 최소 개수를 구하는 것이기 때문에 )
    static int answer = Integer.MAX_VALUE;
    static Integer[] arr;

    //L-동전 갯수
    public void DFS(int L, int sum) {
        if (sum > m) return;
        //지금까지 나온 최소 개수보다는 더 많은 개수 사용 하지 않기
        if (L >= answer) return;
        if (sum == m) {
            answer = L;
        } else {
            for (int i = 0; i < n; i++) {
                DFS(L + 1, sum + arr[i]);
            }
        }
    }

    public static void main(String[] args) {
        Main T = new Main();
        Scanner fb = new Scanner(System.in);
        n = fb.nextInt();
        arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = fb.nextInt();
        }
        //내림차순 정렬하여 큰 단위부터 구하기 ( 갯수 확인 범위 줄이기 )
        //collections쓰려면 int가 아닌 Integer 사용
        Arrays.sort(arr, Collections.reverseOrder());
        m = fb.nextInt();
        T.DFS(0, 0);
        System.out.println(answer);
    }
}

내가 생각한게 아니라 강의에서 설명해준 내용이지만 이렇게도 생각해봐야겠구나해서 올림

 

 

 

출처 인프런 자바(Java) 알고리즘 문제풀이 : 코딩테스트 대비