2020 - 외벽 점검

https://programmers.co.kr/learn/courses/30/lessons/60062#

코딩테스트 연습 - 외벽 점검

[ 문제풀이 ]

한 명부터 모든 친구를 각 영역에 배치하면서 가능한 경우를 찾아주면 되는 완전 탐색 문제이다.

​이동을 시계/반시계 방향으로 할 수 있지만 이는 결국 중복되는 값이기 때문에 한 방향으로만 처리해주도록 하자. 이를 편하게 구현하기 위해 원형을 직선으로 변경해주면 된다.

​예제 1번에서 처리해야 할 영역이 1, 5, 6, 10인 경우 각각 n(12)을 더해줘서 1, 5, 6, 10, 13, 17, 18, 22인 직선으로 만들어준 후 한 방향으로 처리해주면 훨씬 수월하게 해결할 수 있다.

​n 명의 친구를 배치할 수 있는 모든 경우를 뽑아낸 후 각 친구들을 각 영역에 배치해보면서 확인해주면 된다. 가능한지 확인하는 것은 그리디한 방법이기 때문에 dist를 큰 순서부터 처리하는 것이 시간적으로 이득이다.

import java.util.*;

class Solution {
    int answer, len;
    boolean flag;
    boolean[] visit;
    List<Integer> friends, weaks;
    
    public int solution(int n, int[] weak, int[] dist) {
        answer = -1;
        len = weak.length;
        flag = false;
        visit = new boolean[dist.length];
        friends = new ArrayList<>();
        weaks = new ArrayList<>();
        
        //원형을 직선으로 변경
        for (int i = 0; i < len; ++i) {
            weaks.add(weak[i]);
            weaks.add(weak[i] + n); // n을 더해주면 됨
        }
        
        //weak를 오름차순으로 정렬
        Collections.sort(weaks);
        
        //큰 dist 값부터 수행하기 위해 정렬
        Arrays.sort(dist);
        
        //1명부터 최대 친구 수까지
        for (int friendCnt = 1; friendCnt <= dist.length; ++friendCnt) {
            selectFriends(friendCnt, dist);
        }
        
        return answer;
    }
    
    public void selectFriends(int friendCnt, int[] dist) {
        if (flag) return;
        
        if (friends.size() == friendCnt) {
            if (isVaild()) {
                flag = true;
                answer = friendCnt;
            }
            return;
        }
        
        //dist를 배치할 수 있는 모든 경우
        for (int i = dist.length - 1; i >= 0; --i) {
            if (visit[i]) continue;
            
            visit[i] = true;
            friends.add(dist[i]);
            
            selectFriends(friendCnt, dist);
            
            visit[i] = false;
            friends.remove(friends.size() - 1);
        }
    }
    
    public boolean isVaild() {
        for (int i = 0; i < len; ++i) {
            boolean mark = false;
            int idx = 0;
            int start = weaks.get(i);
            
            //i번째 부터 (i+len)번째 까지 처리할 수 있는지 확인
            for (int j = i; j < i + len; ++j) {
                //취약점 지역 - 현재 위치가 dist보다 크면 처리할 수 없음
                if (weaks.get(j) - start > friends.get(idx)) {
                    //현재 위치를 처리할 수 없는 위치로 옮겨줌
                    start = weaks.get(j);
                    idx++;
                    
                    //처리할 수 없는데 모든 dist를 소모하였다면 불가능
                    if (idx == friends.size()) {
                        mark = true;
                        break;
                    }
                }
            }
            if (!mark) return true;
        }
        return false;
    }
}