99클럽 코테 스터디 14일차 TIL / [프로그래머스] 징검다리

오늘의 학습 키워드

---

이분탐색

문제

---

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

• 플랫폼: 프로그래머스
• 문제명: 징검다리
• 난이도: Lv4

풀이

---

import java.util.*;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = distance;
        
        int left = 0;
        int right = distance;
        
        Arrays.sort(rocks);
        
        while(left <= right) {
            int mid = left + (right - left) / 2;
            int rockCnt = 0;
            int front = 0;
            boolean isPossible = false;
            
            for(int back : rocks) {
                int dist = back - front;
                
                if(dist >= mid) {
                    front = back;
                    rockCnt++;
                    
                    if(rockCnt == rocks.length - n) {
                        back = distance;
                        dist = back - front;
                        
                        if(dist >= mid) {
                            left = mid + 1;
                            answer = mid;
                            isPossible = true;
                        }
                        
                        break;
                    }
                }
            }
            
            if(!isPossible) {
                right = mid - 1;
            }
        }
        
        return answer;
    }
}

접근

• 이분 탐색 알고리즘을 활용하여 풀이했습니다.
• left, right의 범위를 도착지점까지의 거리로 설정한 뒤, 가능한 거리의 최솟값을 탐색합니다.
• rocks 배열을 정렬하고, 순회하며 바위 사이의 거리를 계산합니다. 구한 거리를 mid와 비교하며 가능하다면 바위를 추가하고, 가능하지 않다면 제거합니다.
• 제거한 바위 개수가 n과 일치하는 경우, 가능한 경우 중 하나로써 answer에 mid값을 갱신합니다.

소요 시간

1시간