99클럽 코테 스터디 22일차 TIL - Binary Search (프로그래머스 '징검다리')

항해99 코테 스터디 22일차 문제인 프로그래머스의 '징검다리'는 징검다리의 돌을 n개 제거하여 생기는 돌들간의 간격의 최솟값의 최댓값을 구하는 문제다. 난이도는 레벨4이며 이분탐색을 통해 해결할 수 있다.

 

오늘의 문제 - 징검다리 문제 정보

문제 키워드

- 이분탐색(Binary Search)

난이도

- Level 4

 

문제 요약

• 징검다리의 길이 distance와 각 돌의 위치가 배열 rocks로 주어진다.
• 돌을 n개 제거한 뒤 돌간의 간격의 최솟값을 구하는데, 그 최솟값이 최대가 되는 경우를 구하여라.

 

문제 풀이 과정  

• 최솟값의 최댓값... 언제봐도 늘 헷갈리는 개념이다.
• 이분탐색을 이용한 다른 어려운 문제를 풀었던 기억이 있어 찾아봤는데, 걔는 '징검다리 건너기'이고 얘는 '징검다리'이다. 징검다리는 다 BS를 쓰는건가...
• 한참을 머리를 싸매다가 결국 프로그래머스에 새로 붙은 AI한테 물어봤더니 아래처럼 얘기를 해줬다. 덕분에 아이디어는 얻을 수 있었다.

 이 문제를 해결하기 위해서, 사용자는 먼저 배열 `rocks`를 정렬한 후에, 출발지부터 도착지점까지 각 바위 사이의 거리를 바탕으로 최소 거리의 최대 값을 찾기 위한 이진 탐색을 진행해야 합니다. 이진 탐색 과정에서는, 설정한 최소 거리(mid 값)를 만족시키기 위해 제거해야 하는 바위의 개수를 계산하고, 이 개수가 제거해야 할 바위의 수 `n`과 비교하여 조건을 만족하는 최소 거리의 최대값을 찾아야 합니다.
 조금 더 구체적인 힌트를 드리자면, 이진 탐색의 각 단계에서 설정한 '최소 거리'를 기준으로 현재 바위와 이전에 선택된 바위 사이의 거리를 비교해야 합니다. 그리고 이 거리가 설정한 '최소 거리'보다 작으면 해당 바위를 제거하는 것으로 간주해야 합니다. 바위를 제거하는 횟수가 `n`보다 크면 탐색 범위를 줄여야 하고, `n`보다 작거나 같으면 탐색 범위를 늘려 최적의 해를 찾아야 합니다.

• 즉, 징검다리 내의 최소 거리가 x가 되기 위해 돌 몇개를 제거해야 되는지를 구하고, 만약 제거해야 되는 숫자가 n보다 크다면 최소 거리 x를 줄이고, n보다 작다면 최소 거리 x를 늘린다. 라는 개념을 이분탐색으로 구현해서 x를 구하는 것이다.
• "최소 거리가 x가 되기 위해 돌 몇개를 제거해야 되는지"는 getDeleteCnt()라는 메서드로 분리하였다.
  • 현재 구간의 너비가 x보다 작다면 돌을 제거해 가면서 제거되는 돌의 개수를 구하였다.
• 이분탐색 메서드 bs()에서는 현재 범위(l~r)의 중간값을 최소 거리 x로 두고 getDeleteCnt() 메서드를 통해 제거할 돌의 개수를 구하였다. 이 값이 n보다 큰지 작은지에 따라 다음 범위를 설정한다.
  • 이 때, 제거할 돌의 개수가 n보다 작거나 같다면 x로 answer값을 갱신한다. 그 이유가 이해가 잘 안가서 AI한테 또 물어봤는데 사실 정확히 이해는 못했다...ㅠㅠ

`if (deleteCnt == n)` 조건에서만 `answer`를 갱신하는 것이 아닌, `deleteCnt <= n`인 모든 경우에 대해 `answer`를 최대값으로 갱신해주어야 합니다. 이유는, 바위를 제거하는 개수가 `n`보다 적을 때도 거리의 최솟값 중 가장 큰 값을 찾아야 하기 때문입니다.
따라서, `if (deleteCnt > n)` 조건문과 그 외의 조건(즉, `deleteCnt <= n`을 만족하는 경우)으로 로직을 분리하여, `deleteCnt <= n`이 만족하는 경우에 대해서도 `answer`를 갱신하도록 변경해야 합니다. 그 결과, 조건이 `n`과 정확히 일치하는 경우뿐만 아니라 `n` 이하의 경우에도 가능한 최대 거리를 탐색할 수 있게 됩니다.

 

• 그리고 항상 좋은 해설을 해주는 분의 해설을 링크로 남겨본다.
  • https://school.programmers.co.kr/questions/31861

 

코드

import java.util.*;

class Solution {
    
    private int answer = 0;
    
    public int solution(int distance, int[] rocks, int n) {
        int len = rocks.length;
        
        // 돌을 전부 제거해야 하는 경우 전체 거리 바로 반환
        if (n == len) return distance;
        
        Arrays.sort(rocks);
        
        // 각 돌 사이의 거리 배열 구하기
        int[] diff = new int[len+1];
        diff[0] = rocks[0];
        diff[len] = distance - rocks[len-1];
            
        for(int i=1; i<len; i++) {
            diff[i] = rocks[i] - rocks[i-1];
        }
        
        // 전체 범위에서 돌 n개 이하로 제거했을 때의 최소 간격을 구함
        bs(diff, 0, distance, n);
        
        return answer;
    }
    
    private void bs(int[] diff, int l, int r, int n) {
        if (l > r) return;
        
        int mid = (l+r) / 2;
        int deleteCnt = getDeleteCnt(diff, mid);
        
        if (deleteCnt > n) {
            bs(diff, l, mid-1, n);
        } else {
            // 제거할 돌의 개수가 n개 이하라면 정답 갱신
            answer = Integer.max(answer, mid);
            bs(diff, mid+1, r, n);
        }
    }
    
    // 최소 간격이 minDist가 되기 위해 제거해야 하는 돌의 개수를 구하는 메서드
    private int getDeleteCnt(int[] diff, int minDist) {
        int cnt = 0;
        int preDist = diff[0];
        
        // 현재 구간의 간격이 최소거리보다 작으면 현재 돌 제거
        for(int i=1; i<diff.length; i++) {
            if(preDist < minDist) {
                cnt++;
                preDist += diff[i];
            } else {
                preDist = diff[i];
            }
        }
        
        // 마지막 구간이 최소거리보다 작으면 돌 하나 더 제거
        if (preDist < minDist) {
            cnt++;
        }
        
        return cnt;
    }
    
}

• 시간복잡도: 이분탐색이니까... O(RlogD)? → R: 돌 개수, D: 전체 거리
• 공간복잡도: O(R + logD) → logD는 재귀함수 스택