[SWEA]#9088 다이아몬드

문제

태영이는 N개의 다이아몬드를 가지고 있다. 각 다이아몬드 크기는 1 이상 10000 이하의 자연수로 나타낼 수 있다.

태영이는 N개의 다이아몬드 중 몇 개를 골라, 애인에게 선물로 주려고 한다.

한편, 태영이는 고른 다이아몬드의 크기가 뒤죽박죽이면 애인이 좋아하지 않을 것이라고 생각하여,

고른 다이아몬드 중 크기 차가 K 이하인 것들을 묶음으로 가져가려고 한다. (단, 묶음은 여러 묶음일 수 있다.)

태영이가 애인에게 선물할 수 있는 다이아몬드의 최대 개수는 얼마인가?

입력

첫 번째 줄에 테스트 케이스의 수 TC 가 주어진다.

이후 TC 개의 테스트 케이스가 새 줄로 구분되어 주어진다. 각 테스트 케이스는 다음과 같이 구성되었다.

첫 번째 줄에 자연수 N, K가 주어진다. (1 ≤ N ≤ 1000, 0≤ K ≤ 10000)

이후 N개의 줄에 다이아몬드의 크기가 주어진다.

출력

각 테스트 케이스마다 ‘#x’(x는 테스트케이스 번호를 의미하며 1부터 시작한다)를 출력하고,

태영이가 선물할 수 있는 다이아몬드의 최대 개수를 출력하라.

예제 입력 1

2       // 테스트 케이스 개수
2 0     // N, K
1       // 다이아몬드 크기
1
3 3
1
6
4

예제 출력 1

#1 2  //첫 번째 테스트 케이스 결과
#2 2	//두 번째 테스트 케이스 결과

풀이

import java.util.*;
 
class Solution
{
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T, N, K;
        T=sc.nextInt();
        ArrayList<Integer> list = new ArrayList<>();
        for(int test_case = 1; test_case <= T; test_case++)
        {
            N=sc.nextInt();
            K=sc.nextInt();
            int[] diamond = new int[N+1];
             
            for(int i=0; i<N; i++) {
                diamond[i]=sc.nextInt();
            }
            Arrays.sort(diamond);
            int start=0;
            int end=0;
            int cnt=0;
            int max=Integer.MIN_VALUE;
            while(end !=N) {
                if(diamond[end]-diamond[start]<=K) {
                    cnt++;
                    end++;
                    if(max<cnt)
                        max=cnt;
                }
                else {
                    cnt--;
                    start++;
                }
            }
            if(max==1) max++;
            System.out.println("#"+test_case+" "+max);
        }
    }
}