[프로그래머스 Level.3] 외벽 점검 (2020 KAKAO BLIND RECRUITMENT) (Java)
문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/60062
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
코딩테스트 연습 > 2020 KAKAO BLIND RECRUITMENT > 외벽 점검
문제 설명
레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 도중에 주기적으로 외벽의 상태를 점검해야 할 필요가 있습니다.
레스토랑의 구조는 완전히 동그란 모양이고 외벽의 총 둘레는 n미터이며, 외벽의 몇몇 지점은 추위가 심할 경우 손상될 수도 있는 취약한 지점들이 있습니다. 따라서 내부 공사 도중에도 외벽의 취약 지점들이 손상되지 않았는 지, 주기적으로 친구들을 보내서 점검을 하기로 했습니다. 다만, 빠른 공사 진행을 위해 점검 시간을 1시간으로 제한했습니다.
친구들이 1시간 동안 이동할 수 있는 거리는 제각각이기 때문에, 최소한의 친구들을 투입해 취약 지점을 점검하고 나머지 친구들은 내부 공사를 돕도록 하려고 합니다. 편의 상 레스토랑의 정북 방향 지점을 0으로 나타내며, 취약 지점의 위치는 정북 방향 지점으로부터 시계 방향으로 떨어진 거리로 나타냅니다. 또, 친구들은 출발 지점부터 시계, 혹은 반시계 방향으로 외벽을 따라서만 이동합니다.
외벽의 길이 n, 취약 지점의 위치가 담긴 배열 weak, 각 친구가 1시간 동안 이동할 수 있는 거리가 담긴 배열 dist가 매개변수로 주어질 때, 취약 지점을 점검하기 위해 보내야 하는 친구 수의 최소값을 return 하도록 solution 함수를 완성해주세요.
제한사항
- n은 1 이상 200 이하인 자연수입니다.
- weak의 길이는 1 이상 15 이하입니다.
- 서로 다른 두 취약점의 위치가 같은 경우는 주어지지 않습니다.
- 취약 지점의 위치는 오름차순으로 정렬되어 주어집니다.
- weak의 원소는 0 이상 n - 1 이하인 정수입니다.
- dist의 길이는 1 이상 8 이하입니다.
- dist의 원소는 1 이상 100 이하인 자연수입니다.
- 친구들을 모두 투입해도 취약 지점을 전부 점검할 수 없는 경우에는 -1을 return 해주세요.
입출력 예
| n | weak | dist | result |
| 12 | [1, 5, 6, 10] | [1, 2, 3, 4] | 2 |
| 12 | [1, 3, 4, 9, 10] | [3, 5, 7] | 1 |
입출력 예에 대한 설명
입출력 예 #1
원형 레스토랑에서 외벽의 취약 지점의 위치는 다음과 같습니다.
친구들을 투입하는 예시 중 하나는 다음과 같습니다.
- 4m를 이동할 수 있는 친구는 10m 지점에서 출발해 시계방향으로 돌아 1m 위치에 있는 취약 지점에서 외벽 점검을 마칩니다.
- 2m를 이동할 수 있는 친구는 4.5m 지점에서 출발해 6.5m 지점에서 외벽 점검을 마칩니다.
그 외에 여러 방법들이 있지만, 두 명보다 적은 친구를 투입하는 방법은 없습니다. 따라서 친구를 최소 두 명 투입해야 합니다.
입출력 예 #2
원형 레스토랑에서 외벽의 취약 지점의 위치는 다음과 같습니다.
7m를 이동할 수 있는 친구가 4m 지점에서 출발해 반시계 방향으로 점검을 돌면 모든 취약 지점을 점검할 수 있습니다. 따라서 친구를 최소 한 명 투입하면 됩니다.
나의 코드
import java.util.*;
// weak의 모든 케이스 생성하여 일직선상으로 생각한 모든 경우 만들고 dist의 모든 케이스 생성하여
// weak의 모든 케이스와 dist의 모든 케이스를 매칭해서 검사를 실시해 점검 될 때가 있는지 체크해여 최솟값 일 때를 구한다.
class Solution {
int[] dist;
int[][] weakCases;
int answer = 0;
public int solution(int n, int[] weak, int[] dist) {
this.dist = dist;
this.answer = dist.length + 1;
weakCases = new int[weak.length][weak.length];
// weak의 모든 케이스 생성 (일직선상으로 생각하고)
for(int i=0; i<weak.length; i++) {
int idx = 0;
for(int j=i; j<i+weak.length; j++) {
if(j < weak.length)
weakCases[i][idx++] = weak[j];
else
weakCases[i][idx++] = weak[j - weak.length] + n;
}
}
// dist로 dist.length 자리 순열 모든 케이스 생성
dfs(0, new boolean[dist.length], new int[dist.length]);
if(answer == dist.length + 1) return -1;
return answer;
}
// distCase 모든 경우 만들고 만들 때마다 distCase로 checkCanInspectWeak 실행
public void dfs(int depth, boolean[] visited, int[] distCase) {
if(depth == distCase.length) {
for(int[] weakCase : weakCases) checkCanInspectWeak(distCase, weakCase);
return;
}
// dist 모든 케이스 생성
for(int i=0; i<distCase.length; i++) {
if(!visited[i]) {
visited[i] = true;
distCase[depth] = dist[i];
dfs(depth + 1, visited, distCase);
visited[i] = false;
}
}
}
// 해당 distCase로 weakCases 검사해서 점검 될 때가 있는지 체크
public void checkCanInspectWeak(int[] dist_case, int[] weak_case) {
int cur = 0;
int next = 0;
int dist_idx = 0;
while(cur < weak_case.length && dist_idx < dist_case.length) {
next = cur + 1;
while(next < weak_case.length && weak_case[next] - weak_case[cur] <= dist_case[dist_idx]) next++;
cur = next;
dist_idx++;
}
if(cur == weak_case.length) answer = Math.min(answer, dist_idx);
}
}
풀이
- 꽤나 어려운 문제여서 다른 사람의 풀이를 보고 이해한 후 풀었다.
- 주어진 weak의 모든 케이스를 만들고 dist로도 만들 수 있는 모든 케이스를 만들어 weak와 dist의 모든 경우에서 검사해서 점검 될 때가 있는지 체크해하여 최솟값으로 검사가 된다면 answer에 업데이트한다.
- 우선 weak의 모든 케이스를 구한다. 모든 원소를 각각 시작점으로 하여 케이스를 만들면 되는데 weak는 원형으로 되어있으므로 일직선상이라고 생각하고 케이스를 만들면 된다.
예를 들어 weak가 [1, 5, 6, 10] 이라면 모든 케이스를 구해보면 [1, 5, 6, 10] , [5, 6, 10, 13] , [6, 10, 13, 17] , [10, 13, 17, 18] 이다. (시작한 원소보다 앞에 있는 원소는 외벽의 길이에서 해당 원소를 더해주면 된다) - 이제 dfs를 이용하여 dist의 모든 케이스를 만들어 weak의 모든 케이스 중에서 검사가 되는 경우를 찾아 최솟값을 찾으면 된다. 따라서 dist의 케이스가 만들어질 때마다 weak의 모든 케이스를 전부 검사하도록 한다.
- 방문한 인덱스를 체크하기 위해서 체크 테이블(visited)을 만들고 dist의 인덱스를 방문할 때마다 체크하며 완전탐색 dfs를 진행한다.
- dist의 케이스(distCase)를 만들기 위하여 dist를 순회하면서 해당 인덱스에 방문하지 않았다면 visited를 true로 변경하고 distCase[해당 depth]에 dist의 해당 인덱스 값을 넣고 depth를 1 증가시키고 다시 dfs()를 재귀 호출한 뒤 visited를 false로 변경한다.
- 이렇게 dfs를 재귀호출 하다 depth가 dist의 길이와 같아지면 해당 한 가지 케이스가 완성된 것이므로 해당 케이스로 weak의 모든 케이스를 for문을 돌면서 검사한다.
- 검사하는 방법은 weak 케이스의 인덱스를 가리킬 cur와 다음 인덱스인 next를 만들고 dist 케이스의 인덱스를 가리킬 dist_idx를 만든 다음 while문을 돌리면서 weak 케이스의 next 값과 cur 값의 차이가 dist_idx의 값 이하라면 한 명이 weak 케이스의 cur 지점과 next 지점을 검사를 할 수 있는 것이므로 next를 증가시키며 반복하고 검사를 하지 못한다면 cur 지점만 검사 가능하므로 cur에 next 값을 넣고 dist_idx도 1 증가시켜 다음 검사 인원으로 검사를 진행하며 반복하면 된다.
- 그리고 검사를 마쳤을 때 cur가 weak 케이스의 길이와 같다면 weak 케이스의 모든 지점이 검사가 된 것이므로 answer와 dist_idx를 비교하여 dist_idx가 더 작다면 answer에 저장한다.
- 만약 answer가 처음에 초기화한대로 나올 수 없는 값인 dist의 길이보다 1 큰 dist.length + 1이라면 모든 케이스를 검사해도 점검이 불가능하다는 것이므로 -1을 반환하고 아니라면 최소 검사 인원이 저장된 answer를 반환한다.