[Algorithm] 외벽점검 프로그래머스 자바
외벽점검.java
import java.util.*;
class Permutation {
private int n;
private int r;
private int[] now;
private ArrayList<ArrayList<Integer>> result;
public ArrayList<ArrayList<Integer>> getResult() {
return result;
}
public Permutation(int n, int r) {
this.n = n;
this.r = r;
this.now = new int[r];
this.result = new ArrayList<ArrayList<Integer>>();
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void permutation(int[] arr, int depth) {
if (depth == r) {
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < now.length; i++) {
temp.add(now[i]);
}
result.add(temp);
return;
}
for (int i = depth; i < n; i++) {
swap(arr, i, depth);
now[depth] = arr[depth];
permutation(arr, depth + 1);
swap(arr, i, depth);
}
}
}
class 외벽점검 {
public int solution(int n, int[] weak, int[] dist) {
//원형은 보통 일자 형태로 변경
ArrayList<Integer> weakList = new ArrayList<Integer>();
//1 5 6 10
for (int i = 0; i < weak.length; i++) {
weakList.add(weak[i]);
}
//11 15 16 20
for (int i = 0; i < weak.length; i++) {
weakList.add(weak[i] + n);
}
//친구의 최소값 찾기 위해
int answer = dist.length + 1;
//순열
Permutation perm = new Permutation(dist.length, dist.length);
perm.permutation(dist, 0);
ArrayList<ArrayList<Integer>> distList = perm.getResult();
//시작 지점
for (int start = 0; start < weak.length; start++) {
// distList -> 순열 list 완전 탐색
for (int i = 0; i < distList.size(); i++) {
int cnt = 1;//친구 한명
int position = weakList.get(start) + distList.get(i).get(cnt - 1);//취약점 시작 위치 + 순열 한 명이 이동할 수 있는 위치 = 현재 위치
for (int index = start; index < start + weak.length; index++) {//시작 위치 부터 취약점 전부 돌면
if (position < weakList.get(index)) {//갈 수 잇는 거리가 다음 취약점 거리보다 짧으면
cnt += 1;// 한명 더 데리고옴
if (cnt > dist.length) {//다 데리고 오면
break;
}
position = weakList.get(index) + distList.get(i).get(cnt - 1);// 다음 위치
}
}
answer = Math.min(answer, cnt); // 최소 친구 수 구하기
}
}
if (answer > dist.length) {// 사람 수 보다 많다면
return -1;
}
return answer;
}
}
취약점을 모두 방문할 수 있는 최소의 친구의 수를 구하는 문제
-> 갈 수 있는거리를 순열로 모든 경우를 만들어 완전 탐색 진행
1. swap을 활용한 순열
import java.util.*;
class Permutation {
private int n;
private int r;
private int[] now;
private ArrayList<ArrayList<Integer>> result;
public ArrayList<ArrayList<Integer>> getResult() {
return result;
}
public Permutation(int n, int r) {
this.n = n;
this.r = r;
this.now = new int[r];
this.result = new ArrayList<ArrayList<Integer>>();
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void permutation(int[] arr, int depth) {
if (depth == r) {
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < now.length; i++) {
temp.add(now[i]);
}
result.add(temp);
return;
}
for (int i = depth; i < n; i++) {
swap(arr, i, depth);
now[depth] = arr[depth];
permutation(arr, depth + 1);
swap(arr, i, depth);
}
}
}
class 외벽점검 {
public int solution(int n, int[] weak, int[] dist) {
//원형은 보통 일자 형태로 변경
ArrayList<Integer> weakList = new ArrayList<Integer>();
//1 5 6 10
for (int i = 0; i < weak.length; i++) {
weakList.add(weak[i]);
}
//11 15 16 20
for (int i = 0; i < weak.length; i++) {
weakList.add(weak[i] + n);
}
//친구의 최소값 찾기 위해
int answer = dist.length + 1;
//순열
Permutation perm = new Permutation(dist.length, dist.length);
perm.permutation(dist, 0);
ArrayList<ArrayList<Integer>> distList = perm.getResult();
//시작 지점
for (int start = 0; start < weak.length; start++) {
// distList -> 순열 list 완전 탐색
for (int i = 0; i < distList.size(); i++) {
int cnt = 1;//친구 한명
int position = weakList.get(start) + distList.get(i).get(cnt - 1);//취약점 시작 위치 + 순열 한 명이 이동할 수 있는 위치 = 현재 위치
for (int index = start; index < start + weak.length; index++) {//시작 위치 부터 취약점 전부 돌면
if (position < weakList.get(index)) {//갈 수 잇는 거리가 다음 취약점 거리보다 짧으면
cnt += 1;// 한명 더 데리고옴
if (cnt > dist.length) {//다 데리고 오면
break;
}
position = weakList.get(index) + distList.get(i).get(cnt - 1);// 다음 위치
}
}
answer = Math.min(answer, cnt); // 최소 친구 수 구하기
}
}
if (answer > dist.length) {// 사람 수 보다 많다면
return -1;
}
return answer;
}
}
class Permutation {
private int n;
private int r;
private int[] now;
private ArrayList<ArrayList<Integer>> result;
public ArrayList<ArrayList<Integer>> getResult() {
return result;
}
public Permutation(int n, int r) {
this.n = n;
this.r = r;
this.now = new int[r];
this.result = new ArrayList<ArrayList<Integer>>();
}
public void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public void permutation(int[] arr, int depth) {
if (depth == r) {
ArrayList<Integer> temp = new ArrayList<>();
for (int i = 0; i < now.length; i++) {
temp.add(now[i]);
}
result.add(temp);
return;
}
for (int i = depth; i < n; i++) {
swap(arr, i, depth);
now[depth] = arr[depth];
permutation(arr, depth + 1);
swap(arr, i, depth);
}
}
}
위의 경우 순서를 지키면서 결과값은 나오지 않음 -> 순서를 지키면서 순열값이 나오는 경우 (visited 배열 이용하기)
// 순서를 지키면서 n 개중에서 r 개를 뽑는 경우
// 사용 예시: perm(arr, output, visited, 0, n, 3);
static void perm(int[] arr, int[] output, boolean[] visited, int depth, int n, int r) {
if (depth == r) {
print(output, r);
return;
}
for (int i=0; i<n; i++) {
if (visited[i] != true) {
visited[i] = true;
output[depth] = arr[i];
perm(arr, output, visited, depth + 1, n, r);
output[depth] = 0; // 이 줄은 없어도 됨
visited[i] = false;;
}
}
}
2. 원형은 보통 일자 형태로 변경
1 5 6 10 -> 1 5 6 10 13 17 18 22
//원형은 보통 일자 형태로 변경
ArrayList<Integer> weakList = new ArrayList<Integer>();
//1 5 6 10
for (int i = 0; i < weak.length; i++) {
weakList.add(weak[i]);
}
//13 17 18 22
for (int i = 0; i < weak.length; i++) {
weakList.add(weak[i] + n);
}
참고
https://bcp0109.tistory.com/14
Author And Source
이 문제에 관하여([Algorithm] 외벽점검 프로그래머스 자바), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@jifrozen/Algorithm-외벽점검-프로그래머스-자바저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)