[Node.js] level 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

 

 

풀이

투 포인터 문제이며, 슬라이딩 윈도우로 풀어볼까 생각했지만 입력되는 배열의 길이가 상당히 길어 모든 길이의 경우를 판단하기 힘들것 이라 생각해 투 포인터 알고리즘을 이용해 풀이했다.

 

코드에서 sol 함수가 메인 함수이며, 투포인터 알고리즘 답게 배열을 정렬한 뒤 lp와 rp를 0부터 시작해서 개미들간의 거리가 D 이하일 때 개미의 수가 가장 많은 수를 찾는 함수이다.

 

거리가 가깝다면 rp를 1 증가시켜주고, 너무 멀다면 lp를 1 증가시켜준다.

 

코드

// Run by Node.js
const readline = require('readline');

const sol = (n, limit, arr) => {
	let answer = 0;
	let lp = 0;
	let rp = 0;
	
	arr.sort((a, b) => a - b);
	
	while(lp < n && rp < n){
		const width = arr[rp] - arr[lp];
		const antNum = rp - lp + 1;
		if(width <= limit) {
			answer = Math.max(answer, antNum);
			rp++;
		}
		else if(width > limit) {
			lp++;
		}
	}
	return n - answer;
}

(async () => {
	let rl = readline.createInterface({ input: process.stdin });
	let input = []
	
	for await (const line of rl) {
		if(input.length < 2) input.push(line.split(' ').map(Number));
		if(input.length === 2) rl.close();
	}
	console.log(sol(input[0][0], input[0][1], input[1]));
	process.exit();
})();