프로그래머스 - 외벽점검

해당 알고리즘 자료는 제가 직접 푼 것도 있지만 다른 분들의 풀이과의 비교를 통해 더 나은 알고리즘을 공부하기 위해 정리한 것들입니다.

프로그래머스 - 외벽점검

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

풀이 : Bit-Masking을 이용하여 외벽점검에 필요한 인원을 체크

import java.util.*;

class Solution {
   	static int m;
	static int [] weak, dist;
	static int [][] cache; // 메모이제이션
	static final int INF = 987654321;
    public int solution(int n, int[] w, int[] d) {
   	m = n;
	weak = w;
	Arrays.sort(d);
	dist = new int [d.length];
	for (int i = 0; i < d.length; i++) { // 최소 인원으로 점검하기 위해 내림차순으로 정렬
		dist[i] = d[d.length-1-i];
	}
	cache = new int[dist.length+1] [1 << weak.length]; // // 1 뒤로 weak.length 만큼 0을 부여한 뒤 이진수로 전환
	for(int [] i : cache) Arrays.fill(i, -1);
		
	int answer = dp(0, 0);
    	return answer == INF ? -1 : answer;
    }

   private static int dp(int n, int mask) { // n명이 비트 mask 만큼 체크했다. 추가로 몇명이 더 필요하나?
	if(cache[n][mask] != -1) return cache[n][mask];
	if(mask == (1 << weak.length) - 1 ) return cache[n][mask] = 0; // 외벽을 전부 점검
	if(n == dist.length) return INF;
	int ret = INF;
	for (int i = 0; i < weak.length; i++) { // weak를 차례로 시작점으로 점검
		if((mask & (1 << i)) == 0) ret = Math.min(ret, dp(n+1, mask | bit(i, dist[n])) + 1);
		// mask의 i번째 비트가 활성화 되지 않으면 
	}
	return cache[n][mask] = ret;
	}
   private static int bit(int i, int j) { // 비트를 이용하여 외벽의 상태를 점검했는지 확인
	int cur = weak[i];
	int bit = 1 << i;
	while(true) {
		i = (i+1) % weak.length; // 다음 weak
		int next = weak[i];
		int curDist = next > cur? next-cur : m - cur + next; // weak 간의 간격 체크
		if(cur == next || curDist > j) break; // 전부 체크했거나 거리가 더 커졌으면 break
        	bit |= (1 << i); // i번째 비트 활성화
	}
	return bit;
	}
}