[프로그래머스] Lv.4 징검다리 (Java)

문제 링크

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

프로그래머스

 

문제 설명

---

💡 아이디어

도착 지점 distance는 최대 1,000,000,000이므로 완전탐색을 통해 찾으면 분명 시간 초과가 나올 것입니다.

따라서 이 문제는 이분탐색을 사용해 각 지점 사이의 거리의 최솟값을 구하도록 하겠습니다.

 

 

📃 풀이과정

 

1. 이분탐색을 위해 출발지점을 left에 넣고 도착지점을 right에 넣어두어 탐색을 시작합니다.

int left=0; //출발지점
int right=distance; //도착지점

 

2. 돌의 위치를 나타내는 rocks배열은 순서가 섞여있기 때문에, 돌 사이 거리를 구하기 위해 정렬합니다.

Arrays.sort(rocks);

 

3. 이분탐색을 구현하기 위해 while문에 left가 right보다 크지 않을 때까지 반복문을 진행해 줍니다.

 

4. left와 right의 절반인 half를 구해주고, 여기서 half는 돌 사이 거리의 최솟값을 나타냅니다.

int half=(left+right)/2;

 

5. while문 안에 반복문을 돌면서 출발지점부터 도착지점까지 돌 사이의 거리가 half보다 작으면

해당 돌을 제거하여 총 몇 개의 돌이 제거되는지 구합니다.

int removeRock=0; //제거해야 할 돌 개수
int befRock=0; //이전 돌 위치

for(int i=0;i<rocks.length;i++){
    if(rock[i]-befRock>=half) befRock=rocks[i]; //돌 제거하지 않으면 이전 돌 위치를 변경
    else removeRock++;
}

 

6. 만약 제거할 돌 개수가 n개 보다 크다면 돌 사이의 거리를 너무 큰 것으로

     => right를 half-1로 재설정해 범위를 [left ~ half-1]로 만들고 while문을 돌면서 다시 탐색합니다.

 

7. 만약 제거할 돌 개수가 n이하이면

     => answer에 half값을 저장하고, 최댓값을 찾기 위해 범위를 [half+1 ~ right]로 다시 탐색합니다.

if(removeRock>n){ //바위를 더 많이 제거해야 할 경우
    right=half-1;
}
else{
    answer=half;
    left=half+1;
}

 

8. 이 과정을 left가 right보다 커질 때까지 반복하고, 반복문을 나왔을 때의 answer값이 최댓값입니다.

 

---

전체코드

import java.util.*;
class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        
        int left=0;//출발지점
        int right=distance;//도착지점
        
        Arrays.sort(rocks);// 돌 사이 거리를 알기 위해 정렬.
        
        while(left<=right){
            
            int half=(left+right)/2;
            
            
            int removeRock=0; //제거해야 할 돌 개수
            
            int befRock=0;//이전 돌 위치
            for(int i=0;i<rocks.length;i++){
                if(rocks[i]-befRock>=half) befRock=rocks[i];
                else removeRock++; //최소거리보다 작으면 돌 삭제 개수 추가
            }
            if(distance-befRock<half) removeRock++; // 마지막 돌과 도착 지점도 해줘야함.!!
            
            
            //System.out.println(left+" "+right+" "+half+" : "+rockNum+" "+answer);
            
            if(removeRock>n){//바위를 더 많이 제거했을 때
                right=half-1;
            }else{
                answer=half;
                left=half+1;
            }
        }
        
        return answer;
    }
}