문제설명
- 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!면 모든 경우를 탐색하기 충분하다.