[구름LEVEL] 개미 집합의 지름 (Java)

구름LEVEL

접근 방식

투포인터를 사용하여 순차적으로 탐색하며 해결할 수 있는 문제이다. 지름(D) 이하에서 제거할 개미의 수를 최소로 만든다는 건 바꿔말하면 조건에 맞는 개미 숫자를 최대한으로 보존해야함을 의미한다. 즉, 개미들의 위치가 정렬되어 저장된 배열을 포인터 두 개로 완전탐색하여 모든 경우의 수에 대해 최대 개미수를 갱신하면 되는 것이다. 포인터 begin이 고정된 상태에서 포인터 end는 조건(D 이하) 내에서 최대한 진행하여 maxAnts를 갱신한다. 조건을 벗어나면 begin을 증가시키고 다시 거기서부터 end가 탐색을 시작한다. begin과 end는 같은 곳에서 시작해 끝까지 탐색하며 begin은 느린 포인터, end는 빠른 포인터이다.

 

로직 설명

- 개미의 수 n과 지름 d 저장

- int[] arr에 전체 개미의 위치 저장

- arr 배열 정렬

- begin과 end가 둘 다 n 이하인 동안 반복하며:

  1) 현재 구간의 길이(length)와 개미의 수(numOfAnts) 구하기

  2-1) length가 d 이하이면 개미의 수를 비교하여 최대 개미 수(maxAnts) 갱신하고 포인터 end 증가

  2-2) d를 넘어가는 경우 begin 증가

- 제거할 개미 수(전체 개미 - 최대 개미) 출력

 

작성 코드

import java.io.*;
import java.util.stream.Stream;
import java.util.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] input = br.readLine().split(" ");
		int n = Integer.parseInt(input[0]);
		int d = Integer.parseInt(input[1]);
		int[] arr = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

		Arrays.sort(arr);
		
		int begin = 0, end = 0;
		int maxAnts = 0;
		
		while(begin < n && end < n){

			int length = arr[end] - arr[begin];
			int numOfAnts = end - begin + 1;
			
			if(length <= d){
				if(maxAnts < numOfAnts){
					maxAnts = numOfAnts;
				}
				end++;
			}else{
				begin++;
			}
		}
		
		System.out.println(n - maxAnts);
	}
}