[프로그래머스/이진탐색] lv3. 입국심사, lv4. 징검다리 (JavaScript)

프로그래머스 고득점 키드 중 이진탐색 두 문제입니다.

Parametric Search 문제들은 처음 접하게 되었는데,

1. 탐색 대상 수가 몇만, 몇십만 등 큰 수이면 일단 이진탐색을 의심해보고,
2. 이진탐색의 대상을 어떤 것으로 둘 것인지 확인하고,
3. 다음 탐색으로 넘어갈 때 조건은 어떤 것인지 확인하는 것이 관건이었습니다.
   • 이상-이하, 미만-초과 등
   • 최소값을 구하는 경우, 구하는 front 값 나올 때까지 올려서 return
   • 최대값을 구하는 경우, 구하는 rear 값 나올 때까지 내려서 return

lv3. 입국심사

• 이진탐색 대상 : 문제에서 구하는 소요 시간, 0~MAXTIME 구간을 탐색

/**
 * @param {number} n  대기인원, 1~1,000,000,000
 * @param {number[]} times  입국 심사대, 각 심사대별 소요 시간, length: 1~100,000, 시간: 1~1,000,000,000
 * @returns {number}  최소 소요 시간
 */
const solution = (n, times) => {
  
  	// 1명의 심사원이 1번에 1,000,000,000분, 대기인원 1,000,000,000인 경우
	const MAXTIME = 1000000000 * 1000000000;
  
	let front = 0;
	let rear = MAXTIME;
	while (front <= rear) {
		const mid = Math.floor((front + rear) / 2);
      
		// 특정 소요시간에서 몇명이 심사를 마치는지 확인
		let finished = 0;
		for (const ctime of times) {
			finished += Math.floor(mid / ctime);
          
			// 심사 마친 인원이 대기인원 보다 많아지면 loop 종료
			if (finished >= n) break;
		}
      
		// 심사 마친 인원이 대기인원 보다 많은 경우 down
		// 심사 마친 인원이 대기인원 보다 적거나 동일한 경우 up
		finished >= n ? (rear = mid - 1) : (front = mid + 1);
	}
	return front;
};

lv4. 징검다리

이 문제는 이진탐색 대상을 무엇으로 정해야할지부터 어려워서,
jkh2801님 블로그 참고했습니다.

• 이진탐색 대상: 조건을 만족하는 바위 사위 거리, 0 ~ distance
  • 예시에 너무 집중하면 오히려 풀기 어려워지는 문제인 듯
  • 조건을 다르게 표현하면, n개의 바위가 없어질 수 있는 최대 거리를 찾는 것
• 모든 바위 사이 거리를 구하게 되면 너무 연산이 많아지기 때문에 중간에 비교 바위를 바꿈

/**
 * @param {number} distance 출발지점에서 도착지점까지 거리, 1 ~ 1,000,000,000
 * @param {number[]} rocks 현재 바위들의 위치, length : 1 ~ 50000
 * @param {number} n 제거할 바위 개수, 1~rocks.length
 * @returns {number} 모든 경우의 바위 사이 최소값들 중 최대값
 */
const solution = (distance, rocks, n) => {
	const START = 0;
	let front = START;
	let rear = distance;
  
  	// 모든 바위, 출발지점, 도착지점 사이 거리를 구하기 위해 distance 추가
  	// 바위 위치 정렬
	rocks.push(distance);
	rocks = rocks.sort((a, b) => a - b);
	while (front <= rear) {
      
		// 현재 loop에서 최소거리      	
		const mid = Math.floor((front + rear) / 2);
      
		// 현재 비교대상; 출발지점에서 시작
		let cRock = START;
      
		// 사라지는 바위 수
		let cnt = 0;
      
		// 모든 바위, 도착지점과 비교
		// 두 바위 사이 거리가, 현재 최소거리 보다 작으면 사라질 수 있음
		// 반대 경우면 사라질 수 없는 바위이므로, 현재 바위를 비교대상으로 변경
		for (const rock of rocks) {
			rock - cRock < mid ? cnt++ : (cRock = rock);
		}
      
		// 현재 최소거리에서 사라질 수 있는 바위수가 n 보다 많으면 줄여야 함
		cnt > n ? (rear = mid - 1) : (front = mid + 1);
	}
	return rear;
};