Problem2

문제설명

- int[] numbers가 있다. 

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

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

- 최소 swap 횟수를 구한다.

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

---

입출력 정보

input

- int k

- int[] numbers

 

output

int answer(최소 swap 횟수)

---

Code

Solution.class

package jason.socar.problem2;


import java.util.*;

public class Solution {

    static Set<Integer> answerSet = new HashSet<>();
    static int sum=0;
    public int solution(int k, int[] numbers) {


        permutation(numbers, 0, 0, k, numbers.length);

        int answer = answerSet.stream().min(Integer::compare).orElse(-1);
        System.out.println(sum);
        return answer;


    }

    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) {
                    flag = false;
                    break;
                }

            }
            if (flag)
                answerSet.add(cnt);

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

        for (int i = depth; i < N; i++) {

            swap(numbers, depth, i);
            //swap 발생
            if (depth != i)
                permutation(numbers, depth + 1, cnt + 1, k, N);
                //depth==i
                //swap 발생 X
            else
                permutation(numbers, depth + 1, cnt, k, N);

            swap(numbers, depth, i);
        }
    }

    static void swap(int[] numbers, int depth, int i) {
        int tmp = numbers[depth];
        numbers[depth] = numbers[i];
        numbers[i] = tmp;
    }
}

 

Problem2.class

package jason.socar.problem2;

public class Problem2 {

    public static void main(String[] args) {
        int k=3;
        int[] numbers={3,7,2,8,6,4,5,1};
//        int[] numbers= {10,40,30,20};
        int answer=new Solution().solution(k, numbers);
    }
}

---

후기

swap의 경우의 수를 떠올리기 힘들었는데, 순열을 생각하니 이해가 됐다. 순열의 각 경우는 swap의 결과로 봐도 무방하다.

그리고 n의 범위가 8이하이기 때문에 모든 경우를 확인할 수 있었다. 최악의 시간복잡도가 8!면 모든 경우를 탐색하기 충분하다.

---

참고

https://bcp0109.tistory.com/14