[프로그래머스] LV.4 징검다리 (JS)

KG·2021년 5월 10일

알고리즘

목록 보기

46/61

문제

출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다.
예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 [2, 14, 11, 21, 17] 지점에 놓여있을 때 바위 2개를 제거하면 출발지점, 도착지점, 바위 간의 거리가 아래와 같습니다.

제거한 바위의 위치	각 바위 사이의 거리	거리의 최솟값
[21, 17]	[2, 9, 3, 11]	2
[2, 21]	[11, 3, 3, 8]	3
[2, 11]	[14, 3, 4, 4]	3
[11, 21]	[2, 12, 3, 8]	2
[2, 14]	[11, 6, 4, 4]	4

위에서 구한 거리의 최솟값 중에 가장 큰 값은 4입니다.

출발지점부터 도착지점까지의 거리 distance, 바위들이 있는 위치를 담은 배열 rocks, 제거할 바위의 수 n이 매개변수로 주어질 때, 바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 solution 함수를 작성해주세요.

제한

도착지점까지의 거리 distance는 1 이상 1,000,000,000 이하입니다.
바위는 1개 이상 50,000개 이하가 있습니다.
n 은 1 이상 바위의 개수 이하입니다.

입출력 예시

distance	rocks	n	return
25	[2, 14, 11, 21, 17]	2	4

풀이

전에 풀었던 카카오 코테에서 이 문제와 유사한 문제이다. 제목부터가 겹치고 접근 방식 역시 이분탐색으로 동일하다. 도착지점까지의 거리 distance가 최대 10억이기 때문에 시간복잡도를 고려해야 하는데 O(logN)의 시간복잡도인 이분탐색이 그 접근방법으로 적절해 보인다.

이분탐색 사전작업

위에 링크된 문제와 다르게 해당 문제에서는 구해야 하는 값이 n개의 돌을 제거했을때 남아있는 돌들 간의 거리의 최소값 중에 가장 큰 값이다. 만약 입출력 예시처럼 5개의 rocks가 주어지고 그 중에서 2개를 제거해야 하는 경우의 수는 5C2와 같다. 모든 조합을 구해 각각 돌의 거리를 계산하는 것은 당연히 주어진 시간복잡도를 초과할 것 이다.

앞에서 이미 이분탐색으로 해당 문제를 접근할 것이라고 명시했기 때문에, 어떻게 이분탐색을 적용할 지 생각해보자. 이분탐색은 보통 정렬된 데이터에서 수행할 수 있는 전제조건이 있다. (위의 카카오 문제에서는 특수한 경우로 정렬되지 않은 상태에서 이분탐색이 가능했다) 그렇다면 주어진 rocks 배열을 정렬하여 진행하는 것이 가능한지 먼저 판단해보자. rocks 배열에는 바위들의 위치가 무작위로 담겨있는데, 이 값은 오름차순 또는 내림차순 정렬하여 접근해도 각 돌들간의 거리를 계산하는데 문제가 없다.

그렇다면 이분탐색 로직을 어떻게 문제에서 원하는 답을 찾는데 이용할 수 있을까? 이 역시 위에 링크된 카카오 문제와 동일하게 도착지점까지의 거리 distance를 이용하자. 이 거리는 최소값이 1이고 최대값이 10억이다. 이 둘을 이분탐색의 min과 max로 잡아 그 중간값인 mid값을 계산하도록 하자. 따라서 mid값이 의미하는 것은 거리 최소값의 후보가 될 것이다. 이분탐색을 진행하기 전에 위와 관련된 사전작업을 먼저 구현해주자.

// 이분탐색의 최소, 최대값 설정
// max는 문제에서 주어진 최대값 10억을 할당해도 되고
// 아래처럼 주어진 distance 값 자체를 할당해도 된다.
let min = 1;
let max = distance;
// rocks 배열을 오름차순 정렬
rocks.sort((a,b) => a-b);

while(min <= max) {
  // 중간값(= 최소값 후보)를 계산
  const mid = Math.floor((min+max) / 2);
  
  ...
  
  // 어떤 조건에 따라 최소 및 최대값 갱신
  if (...) {
    max = mid-1;
  } else {
    min = mid+1;
  }
}

거리의 최소값 중 최대값

위에서 보았듯이 mid 값은 거리의 최소값이 될 수 있는 후보이다. 말 그대로 후보이기 때문에 최소값 자체가 아니다. 따라서 이 값이 최소값이 될 수 있는지 검증을 해야 한다.

mid 값은 변수명에서도 알 수 있듯이 이분탐색의 현재 최소값 min과 최대값 max의 중간값이 된다. 즉 현재 최소값이 mid일때, 각 바위 사이의 거리가 mid 보다 작다면 해당 바위는 제거할 수 있다. 이때 제거되는 바위의 개수를 체크해주자. 만약 제거된 바위 개수가 n보다 큰 경우는 당연히 최대값 max의 범위를 mid-1로 줄여서 다시 탐색해야할 것이다. 반대로 제거된 바위 개수가 n보다 작거나 같은 경우는 최소값 min의 범위를 mid+1로 늘여 다시 이분탐색을 진행해주자.

각 바위 사이의 거리는 이미 앞에서 rocks를 정렬해주었기 때문에 쉽게 구할 수 있다. 출발지점에 약간 주의해야 하는데, 첫 출발지점은 항상 0으로 시작한다고 보면 쉽다. 입출력 예시에서 주어진 rocks 배열의 구성은 [2, 11, 14, 17, 21] 과 같다. 이때 각 돌들 사이의 거리는 출발지점부터 도착지점까지 계산하여 [2, 9, 3, 3, 4, 4]이 될 것이다. 첫 원소와 마지막 원소는 각각 출발지점-첫 바위까지의 거리, 마지막 바위-도착지점까지의 거리로 이 역시 거리에 포함된다는 것에 주의하자. 또한 만약 바위를 제거하게 되는 경우에는 돌들의 간격이 재조정되는 것 역시 유의해야 한다. 만약 [2, 9, 3, 3, 4, 4]에서 17과 21번 바위를 제거했다면 [2, 9, 3, 11]의 거리로 계산되어야 한다 (입출력 예시의 1번 사례). 이 두가지를 고려하여 다음과 같이 이분탐색을 마저 구현하자.

while(min <= max) {
  ...
  let remove = 0;	// 제거되는 돌의 개수
  // 제거되지 않는 돌에 가장 가까이 위치한 이전 위치의 바위 값 저장
  let prev = 0;		// 첫 위치는 항상 0이므로 0으로 초기화 
  
  // 오름차순 정렬된 rocks를 차례로 방문하면서
  for(let i = 0; i < rocks.length; i++) {
    // 지금 돌의 위치 - 지금 돌과 가장 가까이 위치한 이전 돌 위치
    // 해당 결과가 mid 보다 작거나 같으면 제거가 가능하다는 뜻
    if(rocks[i] - prev <= mid) {
      remove++;
    } else {
      // 만약 이 값이 mid 보다 크다면 해당 위치의 돌은
      // 현재 mid 값으로는 제거가 불가능한 거리에 위치
      // 따라서 이 값을 prve 값으로 갱신 (이전 위치의 돌)
      prev = rocks[i];
    }
  }
  
  // 제거된 돌의 개수가 n보다 크다면 범위를 줄여야 함
  if(remove > n) {
    max = mid-1;
  } else {
    // n보다 작거나 같은 경우엔 범위를 늘려 재탐색
    min = mid+1;
    // 이때 min의 값은 최소값의 후보 중 하나
    // 최소값 중에서 가장 큰 값을 찾아야 하므로
    // 매번 min값의 최대값을 찾아 갱신해준다.
    answer = Math.max(answer, min);
  }
}

전체코드

Lv.4에 등재된 문제이지만 위에 링크된 카카오 코딩테스트의 Lv.3 문제와 비슷한 난이도인 것 같다. 이분탐색은 항상 느끼지만 문제 자체만으로 바로 해당 방식을 사용해야겠다라는 생각을 하기 힘든 것 같다. 그나마 입력값의 크기가 매우 크고, 정렬된 데이터로 접근이 가능한가에 대해 생각해보면 도움이 조금 될 수 있을 것 같다. 해당 문제는 다음의 목록을 떠올렸다면 쉽게 구현할 수 있다.

이분탐색으로 접근
mid 값을 도달할 수 있는 최소 거리값으로 계산
rocks를 오름차순 정렬하여 각 돌들 간 거리 계산

주석을 제외한 전체코드는 다음과 같다.

function solution(distance, rocks, n) {
  let answer = 0;
  let min = 1;
  let max = distance;
  rocks.sort((a,b) => a-b);
  
  while(min <= max) {
    const mid = Math.floor((min+max) / 2);
    let remove = 0;
    let prev = 0;
    
    for(let i = 0; i < rocks.length; i++) {
      if(rocks[i] - prev <= mid) {
        remove++;
      } else {
        prev = rocks[i];
      }
    }
    
    if(remove > n) {
      max = mid-1;
    } else {
      min = mid+1;
      answer = Math.max(answer, min);
    }
  }
  
  return answer;
}