[프로그래머스 고득점 Kit] 이분탐색

최근 3일동안 이분탐색 백준 강의를 들으면서 개념 자체는 어렵지 느껴지지 않았는데

문제를 풀어보면 알 수 없는 벽에 부딪히는 어려움에 생각처럼 쉽게 문제를 풀 수 없었다.

징검다리 문제를 풀면서 이론과 실전의 갭 차이를 크게 느꼈다.

프로그래머스(Lv 3) : 예산

이 문제는 어렵지 않았다.

X(기준값) : 문제에서 말하는 상한액 (합이 최대가 되는 값) 을 설정하고,
문제에서 설명한대로 그대로 구현하니 답이 나왔다.

long l - Left 값을 초기화 할때, budgets[0] 가장작은 값을 처음 값으로 넣었는데, 0으로 해야 테스트케이스 9번을 통과할 수 있었다.

	public static boolean check(int[] a, int m, long mid ) {
		int sum = 0;
		for(int i=0; i<a.length; i++) {
			if( a[i] < mid ) {
				sum += a[i];
			} else {
				sum += mid;
			}
		}
		
		return sum <= m ? true : false;
	}
	
	public static long solution(int[] budgets, int M) {
		long answer = 0;
        
		Arrays.sort(budgets);
        
		long l = budgets[0]; // 0으로 시작해야 한다.
		long r = budgets[budgets.length-1];
        
		while( l<=r ) {
        	long mid = (l+r)/2;
        	
        	if( check(budgets,M,mid) ) {
        		l = mid + 1; 
        		answer = mid;
        	} else {
        		r = mid - 1; 
        	}
        }
        
        return answer;
    }

프로그래머스(Lv 3) : 입국심사

이 문제는 백준에서 풀었던 놀이기구 문제와 비슷해 보였다.
하지만 결과적으로 보면 더 간단한 코드인데 어렵게 생각하다 시간을 많이 뺏어먹었다.

X분(기준값) : 모든 사람이 심사를 받는데 걸리는 최소 시간 을 설정하고,

X분일 때, 각 심사대의 사람 수를 n값에서 빼어 0보다 작을 경우 break로 빠져나와 이분탐색을 진행하도록 구현한다.

이분탐색

1) 사람수가 많아지면 X분을 낮춘다. ( right = mid - 1 )
2) 사람수가 적어지면 X분을 늘린다. ( left = mid + 1 )

	public static boolean check(int[] a, int n, long mid) {
		long people = n;
    	
		for(int time : a) {
			people -= mid/time;
			if( people < 0 ) {
				break;
			}
		}
    	
		return people > 0 ? true : false; 	
	}
    
	public static long solution(int n, int[] times) {
		long answer = Long.MAX_VALUE;
        
		long left = 0;
		long right = Long.MAX_VALUE/2;
        
		Arrays.sort(times);
		// 모든 사람이 심사를 받는데 걸리는 최소 시간
		while(left <= right) {
			long mid = (left+right)/2;
        	
			if( check(times,n,mid) ) {
				left = mid + 1; 
        		
			} else {
				right = mid - 1;
				answer = mid;
			}
		}
        
		return answer;
	}

프로그래머스(Lv 4) : 징검다리

이 문제가 가장 어려웠다.

1) 기준을 무엇으로 잡을 것인가? - 돌다리 사이 최소 거리
2) 제거를 어떻게 할 것인가? - 제거를 하면서 구현하는 문제가 아니라 이분탐색이라 구현이 막막했다.

기준값을 잡았으니까 바위 좌표가 있는 배열에서 각 돌다리 간의 사이 값(gap)을 구할 수 있다.
gap: 두 돌다리 사이의 물리적인 거리
mid: 돌다리 사이 최소 거리(기준값)

for(int i=0; i<a.length; i++) {
	int gap = (i != a.length ? a[i] - last : d - last);
	if( gap < mid ) {
		cnt ++; // mid(기준값)보다 gap이 더 작으면 cnt ++
	} else {
		last = a[i];
	}
}

cnt가 제거해야하는 돌(n) 갯수보다 크면 기준으로 잡은 mid(기준값)이 큰 값이므로 최소 거리를 좁혀야 하고 r = mid - 1,

반대로 cnt가 제거해야하는 돌(n) 갯수보다 작거나 같으면 mid(기준값)이 작다는 말이므로 최소 거리를 늘려야 한다.l = mid + 1

제거해야하는 돌의 갯수(cnt)와 두 돌다리 사이 최소 거리의 관계를 잘 파악해야 한다.

	public static boolean check(int[] a, int n , int d, int mid) {
		int cnt = 0;
		int last = 0;
		for(int i=0; i<a.length; i++) {
			int gap = (i != a.length ? a[i] - last : d - last);
			if( gap < mid ) {
				cnt ++; // 제거하는 바위 갯수
			} else {
				last = a[i];
			}
		}

		return cnt > n ? true : false;
	}
	
	public static int solution(int distance, int[] rocks, int n) {
		int answer = 0;
        
		Arrays.sort(rocks);
        
		int l = 1;
		int r = distance;
		while( l <= r ) {
        	int mid = (l+r)/2;
        	
        	if( check(rocks,n,distance,mid) ) { // 제거하는 바위 갯수가 n보다 크다면 거리를 좁혀야 할 것이고
        		r = mid - 1;
        	} else {
        		l = mid + 1; // 제거하는 바위의 갯수가 n과 같거나 작다면 거리를 늘려야 합니다.
        		answer = mid;
        	}
        }
        
        return answer;
    }

이론을 안다고 해서 풀 수 있는 문제들이 아니였다.
어떤 기준을 정할 수 있는 통찰력을 기르는 훈련이 필요하다.
'무엇을 이분탐색으로 찾을것인가' 에 대한 해답을 찾아야 한다.