[Java] 9088. 다이아몬드

D4-9088. 다이아몬드

 

문제출처: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Oktj6WMQDFAWY&categoryId=AW7Oktj6WMQDFAWY&categoryType=CODE

SW Expert Academy

 

크기에 대해 다이아몬드 갯수 배열에 저장. 합에 대해 왼쪽 끝자리를 빼고 오른쪽 끝자리를 더하며 묶음의 최대 크기를 찾는다.

 

import java.io.BufferedWriter;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Scanner;

class Solution {
	
	static int[] diamondsCounter = new int[10001];
	public static void main(String args[]) throws Exception {
		Scanner sc = new Scanner(System.in);
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = sc.nextInt();
		int N, K;
		for (int test_case = 1; test_case <= T; test_case++) {
			N = sc.nextInt();
			K = sc.nextInt();
			
			Arrays.fill(diamondsCounter, 0);
			for (int i = 0; i < N; i++) {
				diamondsCounter[sc.nextInt()]++;
			}

			int max = 0;
			
			for (int j = 1; j <= 1 + K; j++) {
				max += diamondsCounter[j];
			}
			
			int sum = max;
			for (int i = 1; i < diamondsCounter.length - K - 1; i++) {
				sum = sum + diamondsCounter[i + K + 1] - diamondsCounter[i];
				if (max < sum)
					max = sum;
			}
			
			bw.write("#" + test_case + " " + max + "\n");
		}

		sc.close();
		bw.flush();
		bw.close();
	}
}