문제 링크

설계

main

if __name__ == '__main__':
	N,D = map(int,input().split())
	ant = sorted(list(map(int,input().split())))
	print(two_pointer(ant,D))

1. 인풋을 받는다.
2. 개미 리스트는 정렬한다. (왜냐하면 투포인터 알고리즘을 사용할 것이기 때문!!)
3. 투포인터 알고리즘을 사용하여 최소 사망 개미를 출력한다.

two_pointer

def two_pointer(lst,d):
	start,end = 0,0
	length = 0
	while start < N and end < N:
		if lst[end]-lst[start] <= d:
			length = max(length,end-start+1)
			end += 1
		else:
			start += 1
	return N-length

정렬된 리스트에서 (최대-최소)가 d 이하인 최대 길이를 구해주는 함수

다만, 우리 문제에서는 개미를 최소한으로 죽이는 것을 묻고 있으므로

length를 그대로 return 하는 것이 아닌

N-length를 구한다.

(개미가 총 6마리고 조건을 만족하는 개미의 최대길이가 5라고 가정하면, 최소로 개미를 죽이는 수가 6-5=1이라는 뜻)

투포인터 동작 과정

개미 9마리이고 허용 지름 = 1

개미의 좌표 = [1,2,2,4,4,4,4,4,5] 라고 가정해보자

시작점과 끝점을 0번으로 초기화한다.

그리고 개미의 지름을 구한다.

case1: 지름 <= 허용 지름

끝점을 증가시키고 최대값을 갱신한다.

case2: 지름 > 허용 지름

시작점을 증가시킨다

왜냐하면 정렬된 상태에서 끝점을 증가시키면 지름을 증가하는 것과 같고

시작점을 증가시키면 지름을 감소시키는 것과 같기 때문이다.

같은 원리로 시작점과 끝점이 N 미만일때까지 반복 하면 아래와 같다.

최종적으로 최대 지름 6을 출력하고 이로써 개미를 죽이는 최소 개수는 9-6=3이다.

전체 코드

def two_pointer(lst,d):
	start,end = 0,0
	length = 0
	while start < N and end < N:
		if lst[end]-lst[start] <= d:
			length = max(length,end-start+1)
			end += 1
		else:
			start += 1
	return N-length
			
if __name__ == '__main__':
	N,D = map(int,input().split())
	ant = sorted(list(map(int,input().split())))
	print(two_pointer(ant,D))