[구름 | Java Lv.2] 개미 집합의 지름 (탐색)

문제

https://level.goorm.io/exam/49060/%EA%B0%9C%EB%AF%B8-%EC%A7%91%ED%95%A9%EC%9D%98-%EC%A7%80%EB%A6%84/quiz/1

구름LEVEL

 

---

접근 

 

개미의 위치가 주어지고, 임의의 두 개미의 거리가 어떤 값보다 작아지게 하는 개미를 제거하는 최소 마리 수(D)를 구해야 한다. 

 

일단 개미 위치를 정렬시키고 제일 작은 것과 큰 것의 차이가 D보다 작으면 0을 return하게 하고, D보다 크다면 슬라이딩 윈도우 알고리즘을 사용해서 개미 수 구하기

 

1. 입력값 저장

2. 개미 위치 정렬

3. 모두 D보다 작은 경우

3. 슬라이딩 윈도우 알고리즘

 

슬라이딩 알고리즘 

https://velog.io/@ninto_2/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

 

 

• left와 right 포인터를 사용하여 현재 윈도우의 시작과 끝을 나타낸다,
• right 포인터를 순차적으로 이동하면서 윈도우 내의 개미 위치 차이가 D를 초과하면 left 포인터를 이동시킨다. 
• 윈도우 내의 최대 개미 그룹 크기를 계산한다. 

 

 

최종 코드

package week7.baek.search;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Ant {
    public static void main(String[] args) throws Exception {
        //1. 입력값 저장
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();

        int N = Integer.parseInt(input.split(" ")[0]);
        int D = Integer.parseInt(input.split(" ")[1]);
//        System.out.println("D = " + D);
//        System.out.println("N = " + N);

        input = br.readLine();
        String[] tmp = input.split(" ");
        int[] ants = new int[N];
        for (int i = 0; i <N; i++) {
            ants[i] = Integer.parseInt(tmp[i]);
//            System.out.print(ants[i]);
        }

        //2. 개미 위치 정렬
        Arrays.sort(ants);

        //3. 개미를 제거할 필요가 없는 경우
        if(ants[ants.length-1] - ants[0] <= D ) {
            System.out.println(0);
            return;
        }

        //4. 슬라이딩 윈도우
        int n = ants.length;
        int left = 0;
        int maxGroupSize = 0;

        // 슬라이딩 윈도우를 사용하여 최대 그룹 크기를 찾습니다.
        for (int right = 0; right < n; right++) {
            // 현재 윈도우의 시작과 끝의 차이가 D를 초과하면 left를 이동합니다.
            while (ants[right] - ants[left] > D) {
                left++;
            }
            // 최대 그룹 크기를 갱신합니다.
            maxGroupSize = Math.max(maxGroupSize, right - left + 1);
        }

        System.out.println(n - maxGroupSize);
    }
}

---

 

출처

https://velog.io/@ninto_2/%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘] 슬라이딩 윈도우 알고리즘