알고리즘 - Practice(1)

// 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 O, 중복 x)의 각 결과를 출력하시오
// 방법 1

public class Practice1_1 {
    void permutation(int[] arr, int depth, int n, int r) {
		if (depth == r) {
        	for (int i = 0; i < n; i++) {
            	System.out.println(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        
        for (int i = depth; i < r; i++) {
        	swap(arr, depth, i);
            permutation (arr,depth + 1, n, r);
            swap(arr, depth, i);
        }
    }
    void swap (int[] arr, int depth, int index) {
    	int tmp = arr[depth];
        arr[depth] = arr[index];
        arr[index] = tmp;
    }

    public static void main(String[] args) {
		//Test code
        int[] arr = {1, 2, 3, 4};
		
        Practice1 p = new Practice1();
        p.permutation(arr, 0, 4, 3);
    }
}

결과값

=> 틀림

---

// 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 O, 중복 x)의 각 결과를 출력하시오
// 방법 1

public class Practice1_2 {
    void permutation(int[] arr, int depth, int n, int r) {
		
        if (depth == r) {
        	for (int i = 0; i < r; i++) {
            	System.out.print(arr[i] + " ");
            }
            System.out.println();
            return;
        }
        
        for (int i = depth; i < n; i++) {
        	swap(arr,depth,i);
            permutation(arr, depth + 1, n, r);
            swap(arr,depth,i);
        }
        
        
    }
    void swap (int[] arr, int depth, int a) {
    	int tmp = arr[depth];
        arr[depth] = arr[a];
        arr[a] = tmp;
    }

    public static void main(String[] args) {
		//Test code
        int[] arr = {1, 2, 3, 4};
		
        Practice1 p = new Practice1();
        p.permutation(arr, 0, 4, 3);
    }
}

결과값

=> 정답

---

---

// 1, 2, 3, 4 를 이용하여 세자리 자연수를 만드는 방법 (순서 O, 중복 x)의 각 결과를 출력하시오
// 방법 2


public class Practice1_1 {
   void permutation(int[] arr, int depth, int n, int r, boolean[] visited, int[] out) {
		if (depth == r) {
       	System.out.println(Arrays.toString(out));
           return;
       }
       
       for (int i = 0; i < n; i++) {
       	if (visited[i] != true) {
           	visited[i] = true;
               out[depth] = arr[i];
               permutation(arr,depth + 1, n, r, visited, out);
               visited[i] = false;
           }
       }
       
   }

   public static void main(String[] args) {
		//Test code
       int n = 4;
       int r = 3;
       int[] arr = {1, 2, 3, 4};
       boolean[] visited = new boolean[n];
       int[] out = new int[r];

       Practice2 p = new Practice2();
       p.permutation(arr, 0, n, r, visited, out);
   }
}

결과값

=> 정답