[프로그래머스] 징검다리 + 이분 탐색 정리

1. 문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/43236

프로그래머스

 

2. 풀이 

딱히 풀이가 복잡하진 않은데, 이 문제를 보고 이분 탐색 개념을 떠올리는 것이 어렵다. 

 

using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;

public class Solution {
    public int solution(int distance, int[] rocks, int n) {
          
        Array.Sort(rocks);
        List<int> rocksList = rocks.ToList();
        rocksList.Add(distance);
        int left = 1; // 거리의 최소값 
        int right = distance; //거리의 최대값 
        
        while(left <= right)
        {
            int median = (left + right) / 2; // 최소 거리
            
            int deleteRock = 0;
            int prevRock = 0;    
            
            foreach(var rock in rocksList)
            {
                if((rock - prevRock) < median) // 임의로 정한 최소거리보다 작다는 것은 결국 빠진 돌
                {
                    deleteRock ++; 
                }
                else
                {
                    prevRock = rock;   
                }
            }
            
            if(deleteRock > n) // median이 너무 큼
            {
                right = median - 1;
            }
            else
            {
                left = median + 1;   
            }
        }
        
        Console.WriteLine(left);
        return left - 1;
    }
}

 

 

3. 세 종류의 이분 탐색에 대한 정리. -> 징검다리 문제에서 return left -1을 한 이유다. 

1. 최대값 찾기 (최대 조건 만족값)	조건을 만족하는 가장 큰 값	left = mid + 1	left - 1
2. 최소값 찾기 (최소 조건 만족값)	조건을 만족하는 가장 작은 값	right = mid - 1	left
3. 특정 값 정확히 찾기 (정확한 값 탐색)	정확한 값이 배열에 있는지 여부	return mid	못 찾으면 예외 or -1

 

경우 1.

int left = 최소값;
int right = 최대값;

while (left <= right)
{
    int mid = (left + right) / 2;

    if (조건을 만족함)
        left = mid + 1;   // 더 큰 값도 시도
    else
        right = mid - 1;  // mid가 너무 큼
}
return left - 1; // 마지막으로 만족한 값

 

경우 2.

int left = 최소값;
int right = 최대값;

while (left <= right)
{
    int mid = (left + right) / 2;

    if (조건을 만족함)
        right = mid - 1;  // 더 작은 값도 시도
    else
        left = mid + 1;   // mid가 너무 작음
}
return left; // 최초로 조건을 만족하는 값

 

경우 3. 

int left = 0, right = arr.Length - 1;

while (left <= right)
{
    int mid = (left + right) / 2;

    if (arr[mid] == target)
        return mid;
    else if (arr[mid] < target)
        left = mid + 1;
    else
        right = mid - 1;
}
return -1; // 못 찾음