[프로그래머스] 외벽 점검

문제

programmers.co.kr/learn/courses/30/lessons/60062

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

문제해결방법

레스토랑이 원형 구조라는 것은 weak의 시작점에 따라 결과가 달라질 수 있다는 것을 나타낸다.

따라서 weak의 시작점을 정하고 친구들을 조합하는 모든 경우에 대하여 외벽을 점검할 수 있는지 확인하고

가능한 경우들에 대해 친구의 최소값을 구한다.

코드

package Programmers;
 
public class Solution_외벽점검 {
    
    public static int min = Integer.MAX_VALUE;
    public static boolean[] v;
    public static int[] rweak, friendDist;
    
    public static boolean check(int s, int e, int friend) {
        int index = s;
        int sum = 0;
        for(int i=0; i<friend; i++) {
            int dis = friendDist[i];
            int start = rweak[index];
            sum = 0;
            for(; index<e; index++) {
                sum += rweak[index]-start;
                start = rweak[index];
                if(sum>dis) break;
            }
            if(index==e) return true;
        }
        return false;
    }
    
    public static void dfs(int s, int e, int friend, int count, int[] dist) {
        if(count>=friend) {
            if(check(s, e, friend) && min>friend) min = friend;
            return;
        }
        for(int i=0; i<friendDist.length; i++) {
            if(v[i]==false) {
                v[i] = true;
                friendDist[count]=dist[i];
                dfs(s, e, friend, count+1, dist);
                v[i] = false;
            }
        }
    }
    
    public static int solution(int n, int[] weak, int[] dist) {
        int answer = 0;
        rweak = new int[weak.length*2];
        friendDist = new int[dist.length];
        v = new boolean[dist.length];
        for(int i=0; i<weak.length; i++) {
            rweak[i] = weak[i];
            rweak[i+weak.length] = weak[i]+n;
        }
        for(int i=0; i<weak.length; i++) {
            for(int j=1; j<=dist.length; j++) {
                dfs(i, i+weak.length, j, 0, dist);    
            }
        }
        answer = min;
        if(answer == Integer.MAX_VALUE) answer = -1;
        return answer;
    }
    
    public static void main(String[] args) {
        int n = 12;
        int[] weak = {1, 5, 6, 10};
        int[] dist = {1, 2, 3, 4};
        System.out.println(solution(n, weak, dist));
    }
}

코드에 대한 피드백이나 더 좋은 아이디어는 언제나 환영입니다.