Today I Learned

일요일에 있을 코테가 groom이라는 플랫폼에서 열려서 여기에 적응하기 위해 문제를 풀어봤다.

CT_개미집합의지름

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

문제

수직선위에 개미 N마리가 있다. 임의의 두 개미 사이중 가장 긴 거리를 개미 집합의 지름이라 하는데, 이를 D 이하로 만들어야한다.
첫째줄에 N D가 입력되고, 둘째줄에 각 개미의 좌표가 공백을 두고 주어진다.
제거해야하는 최소 개미의 수를 구해라

풀이과정

• 입력 처리를 BufferedReader와 StringTokenizer로 처리한다.

• 배열을 오름차순으로 정렬한다.

• left, right, maxWindowSize를 초기화하고 while문을 돌린다.

• 창 가장자리의 변수 차이가 d를 넘으면 left를 올리고, d이내면 max를 재고 right를 한칸 올린다.

• 최종 답변은 n에서 max 창 크기를 빼면 나온다.

Java코드

import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer	st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int d = Integer.parseInt(st.nextToken());
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0; i<n; i++){
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		Arrays.sort(arr);
		int left = 0;
		int right = 0;
		int maxWindowSize = 0;

		while(right<n){
			if(arr[right] - arr[left]>d){
				left++;
			} else {
				maxWindowSize = Math.max(maxWindowSize, right-left+1);
				right++;
			}
		}
		int answer = n - maxWindowSize;
		System.out.println(answer);
	}
}

python 코드

• 한참 다 풀고 블로그를 보니 어쩐지 문제가 익숙하더라니 과거에 네이버 부캠 준비하던 시절에 파이썬으로 풀던 코드가 있었다.

• 한참 코드가 적고 효율적이라 일요일에 그냥 파이썬으로 풀까 싶다..
  아무래도 입출력이 자바는 너무 길고 비효율적이라 그런 것 같다.

• 코드

n, d = map(int, input().split())
ants = list(map(int, input().split()))
ants.sort()

l = 0
max_len = 0

for r in range(n):
	while ants[r] - ants[l] > d:
		l += 1
	max_len = max(max_len, r-l+1)

print(n-max_len)