<Algorithm> 166. 징검다리(Programmers)

1. 징검다리(Programmers)

   사용 알고리즘 :  이분탐색

• 이문제는 알고리즘 카테고리를 보고 문제를 풀었는데도 접근방향이 떠오르지 않았다. 

• 무엇을 이분탐색 재료로 쓸지와 문제가 원하는 조건에 대한 로직을 어떻게 여기에 맞게 구현하느냐 핵심인 것 같았다.

• 이 문제를 모르고 봤을때 이분탐색이 떠오를 수 있을까 라는 생각이 들었고 이분탐색도 많이 풀어봐야 겠다.

문제에 대한 접근&생각

1. 바위를 제거해서 그 사이의 최소값 중 최대값을 구해야함 -> 완전탐색?, 이분탐색?
2. 바위 갯수 & 제거 갯수 50000개 -> 이분탐색 !

내 코드 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

import java.util.Arrays;   public class Solution {      public int solution(int distance, int[] rocks, int n) {         Arrays.sort(rocks);         int start = 0;         int end = distance;         /******************************          * 이분탐색을 활용하여 사이의 최댓값인           * distance를 기준으로 분할한다.           * 이때 내부는 중간값을 목표로 크기비교를          * 통해서 이 중간값에 해당하는 돌 사이          * 최솟값을 구할 수 있는지를 판단하여          *           *******************************/         while (start < end) {             int rm = 0;             int mid = (start+end+1)/2;             int current = 0;             for(int i = 0; i < rocks.length;i++) {                 if(rocks[i] - current < mid)                      rm++; // 사이값이 기준값보다 작을시                           // 바위를 제거해야함                 else                      current = rocks[i];             }             if(rm > n) end = mid -1;             // 지울 바위가 많다는 것은 더 촘촘하게 놓여있으므로             // 기준 값보다 작은 값을 탐색해야 한다.             else start = mid;         }                  return start;      } }   Colored by Color Scripter

cs