문제2

문제설명

- int[] numbers가 있다. 

- 각 요소들은 인접한 요소와 값의 차가 k이하가 되어야 한다.

- k 이하가 안되면 swap을 해서라도 k이하가 되게 만들어야 한다.

- 최소 swap 횟수를 구한다.

- numbers의 길이는 최대 8이다.

 

입출력 정보

input

- int k

- int[] numbers

output

int answer(최소 swap 횟수)

 

Code

import java.util.*;

class solution {

	static Set<Integer> answerSet = new HashSet<>();
    static int sum = 0;
    
	public int solution(int[] numbers, int K) {
        int answer= 0;
        permutation(numbers, 0, 0, K, numbers.length);

        answer = answerSet.stream().min(Integer::compare).orElse(-1);
        return answer;
    }

    public static void permutation(int[] numbers, int depth, int cnt, int k, int N) {
        if(depth == N) {
            sum += 1;
            boolean flag = true;
            for(int i=1; i<numbers.length; i++) {
                if(Math.abs(numbers[i-1] - numbers[i]) > k) {
                    // 인접하는 두 수의 차가 k보다 큰 경우, swap 처리 필요함 -> flag = false;
                    flag = false;
                    break;
                }
            }

            if(flag) answerSet.add(cnt);

            System.out.println(Arrays.toString(numbers));
        }

        for(int i=depth; i<N; i++) {
            // swap
            swap(numbers, depth, i);
            if(depth != i) permutation(numbers, depth+1, cnt+1, k, N);
            // depth == i 일 경우 swap 하지 않음.
            else permutation(numbers, depth + 1, cnt, k, N);
            swap(numbers, depth, i);
        }
    }

    public static void swap(int[] arr, int idx1, int idx2) {
        int tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
    
}