99클럽 코테 스터디 14일차 TIL [이분탐색]

- 오늘의 학습 키워드 : 이분탐색

[문제 이름 : 징검다리  (프로그래머스, Lv 4) ]

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

내가 작성한 코드는 아래와 같다.

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        // 바위 위치 정렬
        Arrays.sort(rocks);

        int answer = 0;
        // 지점 간 최소 거리의 최솟값
        int low = 1;
        // 지점 간 최소 거리의 최댓값
        int high = distance;

        while(low <= high) {
            // 현재 고려 중인 거리의 최소값 (= 거리의 최솟값 중 최댓값)
            int mid = (low + high) / 2;
            if (canRemove(distance, rocks, n, mid)) {
//                System.out.println("mid: " + mid);
                answer = mid;
                low = mid + 1;
            } else {
            // 제거해야 할 바위가 n보다 큰 경우
                high = mid - 1;
            }
        }

        return answer;
    }

    static boolean canRemove(int dist, int[] rocks, int n, int minDist) {
        int removedRocks = 0;
        // 이전 바위 위치
        int prev = 0;

        for(int rock : rocks) {
            // 현재 바위와 이전 바위의 거리 < minDistance인 경우 해당 바위 제거
            if (rock - prev < minDist) {
                removedRocks++;
//                System.out.println("minDist = " + minDist + "일 때, rock: " + rock + ", prev: " + prev + ", removedRocks: " + removedRocks);
                if (removedRocks > n) {
                    return false;
                }
            } else {
                prev = rock;
            }
        }

        // 마지막 구간 체크
        if (dist - prev < minDist) {
            removedRocks++;
        }

        return removedRocks <= n;
    }
}

 

[풀이 과정]

1. 이분 탐색을 하기 위해, rocks 배열을 오름차순으로 정렬한다.

2. 바위 <-> 바위의 최소거리의 최솟값을 low, 바위 <-> 바위의 최소거리의 최댓값을 high로 잡는다. 이때, 초기값을 계산해보면 바위 간 최소 거리는 1이고, 최대 거리는 distance만큼의 거리에 해당한다.

3. 바위 사이의 거리와 minDistance(=mid)값을 계산해보면서, minDistance 값보다 작은 바위는 제거하고, 제거하면서 제거해야 하는 바위수가 n보다 큰지 확인한다.

4. 이때, 최소거리보다 바위가 크다면, 바위를 제거하지 않고 이전 바위 값에 현재 바위 값을 저장한다.

5. 마지막 바위 간의 거리를 위의 로직과 동일하게 체크한다.

6. 만약 이 minDistance (=mid) 값이 제거할 수 있는 바위 개수 (n)보다 크다면, 좀 더 작은 범위에서 탐색을 반복한다.

7. 그것이 아니라, minDistance (=mid) 값이 작거나 같다면, 이를 충분히 만족하므로, 이들의 최댓값을 구하기 위해 좀 더 큰 범위에서 탐색을 반복한다.

 

canRemove()메서드를 떠올리는데 애를 많이 먹은 문제였다.

풀이 시간 : 1시간

 

내일은 2개의 기업에 대한 자기소개서 작성 및 멘토링을 가져볼 것이다.

[참고]

백준과 비슷한 문제들이 몇 개 있다. 아래 url로 들어가서 이분 탐색 문제들을 같이 살펴보면 좋을 것 같다.

2021.11.29 - [Problem Solving/BOJ] - [BOJ 2110] 공유기 설치 (Java)

[BOJ 2110] 공유기 설치 (Java, Python)

 

2021.12.01 - [Problem Solving/BOJ] - [BOJ 1654] 랜선 자르기 (Java)

[BOJ 1654] 랜선 자르기 (Java)

 

2021.11.30 - [Problem Solving/BOJ] - [BOJ 2805] 나무 자르기 (Java)

[BOJ 2805] 나무 자르기 (Java)