징검다리

TPark·2019년 11월 28일
0

알고리즘

목록 보기
7/13

문제출처: https://programmers.co.kr/learn/courses/30/lessons/43236

문제

출발지점부터 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 이상 바위의 개수 이하입니다.

풀이

이 문제는 바위간의 거리를 기준으로 이분탐색법을 통해 풀었는데, 사실 처음에 바위간의 거리를 따로 리스트에 저장하고 거기서 최소값을 차례로 삭제하고 합쳐주는 단순한 방법으로 풀어보려다가 도저히 통과가 안되서 결국 이분의 풀이를 참고했다...
풀이과정은 아래와 같다.

  • rocks를 오름차순으로 정렬한다
  • mid를 기준으로 현재 바위와 이전 바위의 거리가 더 작거나 같으면 현재 바위를 제거해주고 cnt를 늘린다
  • 만약 제거되지 않았다면 현재 바위와 이전 바위의 거리가 최소값인지 확인한다
  • 마지막 바위와 도착지점 사이의 거리는 for loop 후에 따로 확인해준다
  • 만약 cnt가 n보다 작거나 같다면 현재의 최소값이 최소값 중 최대값인지 확인한다

코드

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks); //바위 거리순으로 정렬
        int min = 1;
        int max = distance;
        int maxDist = 0;
        
        // 바위의 거리를 기준으로 이진탐색
        // mid 보다 거리가 적은 바위를 지웠을때 지운 바위의 수가 n보다 작거나 같아야한다
        while(min <= max) {
            int mid = (min + max) / 2;
            int cnt = 0;
            int prev = 0;
            int minDist = Integer.MAX_VALUE;
            for (int i = 0; i < rocks.length; i++) {
                if (rocks[i] - prev <= mid) {
                    cnt++;
                }
                else {
                    minDist = Math.min(rocks[i] - prev, minDist);
                    prev = rocks[i];
                }
            }
            //마지막 바위는 그 전의 돌과 도착지점을 모두 확인해야함
            if (distance - prev <= mid) {
                cnt++;
            }
            else {
                minDist = Math.min(distance - prev, minDist);
            }
            if (cnt <= n) {
                maxDist = Math.max(maxDist, minDist);
                min = mid + 1;
            }
            else {
                max = mid - 1;
            }
        }
        
        return maxDist;
    }
}

0개의 댓글