<Lv.4> 징검다리 (프로그래머스 : C#)

https://school.programmers.co.kr/learn/courses/30/lessons/43236

📕 문제 설명

출발지점부터 도착지점 사이에 바위들이 놓여있을 때 바위를 n개 제거한 후 각 지점 사이의 거리의 최솟값 중 가장 큰 값을 반환하기

• Input
  출발지점부터 도착지점까지의 거리, 바위들의 위치를 담은 배열, 제거할 바위 수 n
• Output
  바위 n개 제거 후 각 지점 사이 거리의 최솟값 중 가장 큰 값

예제

풀이

계속 답이 안구해져서 왜지 하고있었는데 마지막 돌과의 거리를 위해 distance를 붙인 rockList를 사용해야 풀렸다 ㅎ..

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

public class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Array.Sort(rocks);
        List<int> rockList = rocks.ToList();
        rockList.Add(distance);
        
        int left = 0;
        int right = distance;
        int mid = 0;
        
        while (left <= right)
        {
            mid = (left + right) / 2; // mid = 거리의 최솟값
            
            int deletedRockCount = 0;
            int prevRock = 0;
            foreach (int rock in rockList)
            {
                if (rock - prevRock < mid) // 두 바위 사이 지정한 최소보다 작은경우
                {
                    deletedRockCount += 1; // 해당 rock 제거 (즉, prevRock은 유지)
                }
                else
                {
                    prevRock = rock;
                }
                
                if (deletedRockCount > n) break;
            }
            
            if (deletedRockCount > n)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return left - 1;
    }
}

결과