[JAVA] [SWEA] 9088. 다이아몬드

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

 

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

 

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

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

 

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

 

이 문제는 D4 답게 최소한의 효율만 생각하면서 풀었다. 완탐을 하더라도 가능은 할 것 같으나 별다른 좋은 수가 떠오르지 않아 적당히 효율만 챙기면서 하였다.

 

1. 완탐을 할 것이나 그나마 조금의 효율을 위해 다이아 크기의 min값과 max값을 입력 시 구해 두었다.

2. 다이아의 최소 크기 부터 최대 크기인 10000에 각 개수를 입력 시 구해두었다.

3. min값과 max값 사이의 다이아에서 K 이하의 다이아 개수를 다 더하여 최대 값을 구하였다.

( 중간에 for문에서 삼항연산자는 조금 귀찮더라도 메모리를 챙기기 위해 다이아 배열이 10001까지이고 만약 i가

9999번째고 K가 5라면 런타임 에러가 날 수 있기에 유동적으로 값이 변할 수 있게 하였으나 이 글을 작성하면서 생각해보니 그냥 max값 - K까지만 확인하면 더욱 속도가 날 수 있을 것 같다.

 

전체 소스 코드는 다음과 같다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Solution {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int T = Integer.parseInt(br.readLine());
		for(int t=1; t<=T; ++t) {
			String[] str = br.readLine().split(" ");
			int n = Integer.parseInt(str[0]);
			int k = Integer.parseInt(str[1]);
			int[] dia = new int[10001];
			int max = 0;
			int min = 10001;
			for(int i=0; i<n; ++i) {
				int size = Integer.parseInt(br.readLine());
				if(max < size) {
					max = size;
				}
				if(min > size) {
					min = size;
				}
				dia[size]++;
			}
			int result = 0;
			for(int i=min; i<max+1; ++i) {
				int sum = 0;
				for(int j=i; j<(i+k+1 > 10001? 10001 : i+k+1); ++j) {
					sum += dia[j];
				}
				if(sum > result) {
					result = sum;
				}
			}
			bw.write("#"+t+" "+result+"\n");
		}
		bw.close();
		br.close();
	}
}