다이아몬드

Software Expert Academy [9088] 다이아몬드

풀이

주의사항 : 하나의 다이아몬드를 기준으로 묶음 처리를 하는것이 아닌, 묶음 안에 있는 다이아몬드가 전부 서로 K이하여야 한다
picK() : j가 i+1부터인 이유는 0~i까지는 이전에 i for문에서 처리했기 때문.

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
 
public class Solution {
    static int N, K, ans;
    static int[] dia;
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
 
        for (int tc = 1; tc <= T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            N = Integer.parseInt(st.nextToken());
            K = Integer.parseInt(st.nextToken());
            ans = 0;
            dia = new int[N];
 
            int min = 987654321;
            int max = 0;
            for (int i = 0; i < N; i++) {
                int num = Integer.parseInt(br.readLine());
                dia[i] = num;
                if (num < min)
                    min = num;
                if (num > max)
                    max = num;
            }
 
            Arrays.sort(dia);
            if (max - min > K) {
                pick();
            } else
                ans = N;
            System.out.println("#" + tc + " " + ans);
        }
 
    }
 
    public static void pick() {
        for (int i = 0; i < N; i++) {
            int cnt = 1;
 
            out: for (int j = i + 1; j < N; j++) {
                int diff = Math.abs(dia[i] - dia[j]);
                if (diff <= K) {
                    cnt++;
                } else {
                    break out;
                }
            }
            ans = Math.max(cnt, ans);
        }
    }
}