[코딩테스트] Java 징검다리

제가 공부한 내용을 정리하는 블로그입니다.
아직 많이 부족하고 배울게 너무나도 많습니다. 틀린내용이 있으면 언제나 가감없이 말씀해주시면 감사하겠습니다😁
Programmers 알고리즘 고득점 Kit입니다.

포인트

이 문제는 이분 탐색을 어떤 값으로 하느냐가 포인트였던 것 같습니다. 저는 바위 간의 거리의 최솟값을 기준으로 이분탐색을 진행하였습니다. 해당 바위 사이의 거리가 최솟값보다 크다면 삭제하고, 삭제한 값이 n보다 더 많으면 범위를 재탐색하는 로직으로 설계하였습니다.

 

하지만 해당 문제에서 제거한 바위의 갯수랑 n과 같을때로 설정하면 문제가 틀리고 제거한 바위가 n보다 작거나 같을때로 하면 정답이 되었습니다. 문제의 설명이 빠진 것인지 싶은데 혹시 해당 이유를 아시는 분 있으면 댓글달아주시면 감사드립니다😁

소스코드

import java.util.Arrays;

class Solution {
    public int solution(int distance, int[] rocks, int n) {
        int answer = 0;
        Arrays.sort(rocks);
        
        int left = 1;
        int right = distance;
        
        // 바위의 거리의 최솟값을 기준으로 이분탐색
        while(left <= right) {
            int mid = (left + right) / 2;
            int deleteRocks = 0;
            int prevRock = 0;
            
            for(int rock: rocks) {
                if (Math.abs(rock - prevRock) < mid) {
                    deleteRocks++;
                } else {
                    prevRock = rock;
                }
            }
            
            if (distance - prevRock < mid) {
                deleteRocks++;
            }
            
            if (deleteRocks > n) {
                right = mid - 1;
            } else if (deleteRocks <= n) {
                left = mid + 1;
                answer = mid;
            }
        }
        
        return answer;
    }
}

코드 설명

• 변수 초기화
  • rocks: 바위 위치들을 정렬하여 바위들 사이의 거리를 쉽게 계산할 수 있도록 합니다
  • left: 최소 거리의 시작 값은 1로 설정합니다.
  • right: 최대로 가능한 거리 값은 전체 거리인 distance입니다.
• 이분탐색
  
  • mid: 현재 탐색 중인 거리 값입니다. 이 값은 최소 거리로 유지하면서 바위들을 제거할 수 있는지 확인하려는 값입니다.
  • deleteRocks: 제거된 바위의 갯수입니다.
  • prevRock: 이전 바위의 인덱스입니다. 처음에는 0으로 설정합니다.(초기값)
• 바위들 사이의 간격 체크
  
  • Math.abs(rock - prevRock) < mid: 현재 바위와 직전 바위 사이의 거리가 mid보다 작으면, 이 바위는 제거해야 하므로 deleteRocks를 증가시킵니다.
  • 그렇지 않으면, prevRock을 현재 바위로 업데이트하여 다음 바위와의 거리를 비교할 준비를 합니다.
• if (distance - prevRock < mid) { deleteRocks++; }
  마지막 바위와 거리 체크
• 범위설정
  • deleteRocks > n: 바위를 너무 많이 제거한 경우, mid값을 줄여야 하므로 right = mid - 1으로 범위를 좁힙니다.
  • deleteRocks <= n: 바위 제거 개수가 n개 이하인 경우, mid 값은 유효하므로 left = mid + 1로 범위를 확장하고, answer를 mid로 업데이트하여 더 큰 거리 값도 탐색할 수 있도록 합니다.