프로그래머스 외벽점검 (JAVA)

2020 KAKAO BLIND RECRUITMENT

---

괄호 변환

---

 

지문 요약

친구들을 투입하는 예시 중 하나는 다음과 같습니다.

• 4m를 이동할 수 있는 친구는 10m 지점에서 출발해 시계방향으로 돌아 1m 위치에 있는 취약 지점에서 외벽 점검을 마칩니다.
• 2m를 이동할 수 있는 친구는 4.5m 지점에서 출발해 6.5m 지점에서 외벽 점검을 마칩니다.

그 외에 여러 방법들이 있지만, 두 명보다 적은 친구를 투입하는 방법은 없습니다. 따라서 친구를 최소 두 명 투입해야 합니다.

 

처음에 고민했던 방식은 점과 점 사이의 거리를 기준으로 정렬하여 최대거리의 간선들을 빼가며 탐색하는 방식이었지만, 반례가 생각나서 포기했다.

조금 더 고민한 끝에, 결국 완전탐색의 형태로 진행해야한다는 판단이 섰고, 그대로 진행했다.

 

 

1. 취약지점 배열을 연장한다. ( 마지막 취약지점에서 출발해도 모든 취약지점을 탐색할 수 있도록, weak.length + N 개의 배열로 만든다.)

ex) [1, 3, 5, 7]이고 n = 12로 주어졌다고 가정하면,

[1, 3, 5, 7, 13, 16, 17] 로 만든다.

2. 친구를 분배하는 순서를 순열로 만들고, 만들어진 순열로 탐색이 가능한지 확인한다.

3. 탐색이 가능하면 종료하고 숫자를 출력한다.

 

 

1. 취약지점 배열을 연장한다. ( 마지막 취약지점에서 출발해도 모든 취약지점을 탐색할 수 있도록, weak.length + N 개의 배열로 만든다.)

	private static int[] spreadPoint(int n, int[] weak) {
		int[] spread = new int[weak.length * 2 - 1];
		for (int i = 0; i < weak.length; i++) {
			spread[i] = weak[i];
		}
		for (int i = 0; i < weak.length - 1; i++) {
			spread[i + weak.length] = weak[i] + n;
		}

		return spread;
	}

 

 

 

2. 친구를 분배하는 순서를 순열로 만들고, 만들어진 순열로 탐색이 가능한지 확인한다.

	private static void perm(int depth, int cnt, int[] dist, boolean[] visit, int[] res) {
		if (ans != -1) {
			return;
		}
		if (depth == cnt) {
			check(res);
			return;
		}

		for (int i = 0; i < dist.length; i++) {
			if (visit[i]) {
				continue;
			}
			res[depth] = dist[i];
			visit[i] = true;
			perm(depth + 1, cnt, dist, visit, res);
			visit[i] = false;
		}
	}

 

 

3. 탐색이 가능하면 종료하고 숫자를 출력한다.

	private static void check(int[] res) {
		outer: for (int i = 0; i < weakCnt; i++) {
			int start = i;
			int f = 0;
			for (int j = i; j < i + weakCnt; j++) {
				if (spreadWeak[j] - spreadWeak[start] > res[f]) {
					start = j;
					f++;
				}
				if (f == res.length) {
					continue outer;
				}
			}
			ans = res.length;
			return;
		}
	}

 

코드 전문

class Solution {
    static int ans = -1;
	static int[] spreadWeak;
	static int weakCnt;
public static int solution(int n, int[] weak, int[] dist) {
		weakCnt = weak.length;
		spreadWeak = spreadPoint(n, weak);

		for (int i = 1; i <= dist.length; i++) {
			perm(0, i, dist, new boolean[dist.length], new int[i]);
		}

		return ans;
	}

	private static void perm(int depth, int cnt, int[] dist, boolean[] visit, int[] res) {
		if (ans != -1) {
			return;
		}
		if (depth == cnt) {
			check(res);
			return;
		}

		for (int i = 0; i < dist.length; i++) {
			if (visit[i]) {
				continue;
			}
			res[depth] = dist[i];
			visit[i] = true;
			perm(depth + 1, cnt, dist, visit, res);
			visit[i] = false;
		}
	}

	private static void check(int[] res) {
		outer: for (int i = 0; i < weakCnt; i++) {
			int start = i;
			int f = 0;
			for (int j = i; j < i + weakCnt; j++) {
				if (spreadWeak[j] - spreadWeak[start] > res[f]) {
					start = j;
					f++;
				}
				if (f == res.length) {
					continue outer;
				}
			}
			ans = res.length;
			return;
		}
	}

	private static int[] spreadPoint(int n, int[] weak) {
		int[] spread = new int[weak.length * 2 - 1];
		for (int i = 0; i < weak.length; i++) {
			spread[i] = weak[i];
		}
		for (int i = 0; i < weak.length - 1; i++) {
			spread[i + weak.length] = weak[i] + n;
		}

		return spread;
	}
}