Diamond Collector

알고리즘 구분 : 브루트포스, 투 포인터, 정렬

문제

Bessie the cow, always a fan of shiny objects, has taken up a hobby of mining diamonds in her spare time! She has collected N diamonds (N <= 1000) of varying sizes, and she wants to arrange some of them in a display case in the barn.

Since Bessie wants the diamonds in the case to be relatively similar in size, she decides that she will not include two diamonds in the case if their sizes differ by more than K (two diamonds can be displayed together in the case if their sizes differ by exactly K). Given K, please help Bessie determine the maximum number of diamonds she can display in the case.

입력
The first line of the input file contains N and K (0 <= K <= 10,000). The next N lines each contain an integer giving the size of one of the diamonds. All sizes will be positive and will not exceed 10,000.

출력
Output a single positive integer, telling the maximum number of diamonds that Bessie can showcase.

예제 입력 1
5 3
1
6
4
3
1
예제 출력 1
4

문제 풀이

문제를 이해해보자면, 다이아몬드가 N개 있으며, 가장 작은 size와 가장 큰 size의 차이가 K이하가 되도록 전시를 하고 싶어 한다. 가장 많은 다이아몬드를 전시할 때의 다이아몬드 수를 구하는 것이 문제에서 요구하는 결과다. 전체 다이아몬드의 개수는 1,000개이며, 각 다이아몬드의 size는 10,000을 넘지 않는다. 또한 K 역시 최대가 10,000이다.

먼저 각 다이아몬드의 size가 정렬되지 않은 상태로 입력받게 되므로, 정렬해야 한다.
이후, 이를 투 포인터 알고리즘으로 접근한다면, 전시하는 다이아몬드 중 가장 작은 size를 시작점으로 정하여 반복문을 구현해 각 다이아몬드의 size와 시작점 다이아몬드 size의 차이가 K이상이 될때 break되도록 하여, 시작점과 끝 점을 찾아 이 둘의 차이를 전시할 수 있는 다이아몬드의 총 개수가 될 수 있도록 구현하면 된다.

전체를 완전 탐색하더라도 시간 복잡도는 O(N^2)이며, N <= 1,000이므로, 문제의 시간 제한인 2초 안에 충분히 탐색할 수 있다.

여기서 조심해야 할 것은, 엣지 케이스이다.
아래의 엣지 케이스를 참고하면 좋을 것 같다.

엣지 케이스
Input
200 1000
384
887
778
916
794
336
387
493
650
422
363
28
691
60
764
927
541
427
173
737
212
369
568
430
783
531
863
124
68
136
930
803
23
59
70
168
394
457
12
43
230
374
422
920
785
538
199
325
316
371
414
527
92
981
957
874
863
171
997
282
306
926
85
328
337
506
847
730
314
858
125
896
583
546
815
368
435
365
44
751
88
809
277
179
789
585
404
652
755
400
933
61
677
369
740
13
227
587
95
540
796
571
435
379
468
602
98
903
318
493
653
757
302
281
287
442
866
690
445
620
441
730
32
118
98
772
482
676
710
928
568
857
498
354
587
966
307
684
220
625
529
872
733
830
504
20
271
369
709
716
341
150
797
724
619
246
847
452
922
556
380
489
765
229
842
351
194
501
35
765
125
915
988
857
744
492
228
366
860
937
433
552
438
229
276
408
475
122
859
396
30
238
236
794
819
429
144
12
929
530

Output
200

소스 코드

#include <bits/stdc++.h>

using namespace std;

int n, k;
vector<int> v;
void solve();

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n >> k;
	for(int i = 0; i < n; i++) {
		int input;
		cin >> input;
		v.push_back(input);
	}
	
	solve();
	
	return 0;
}

void solve() {
	int temp;
	int result = 0;
	
	sort(v.begin(), v.end());
	for(int i = 0; i < n; i++) {
		for(int j = i + 1; j < n; j++) {			
			if(v[j] - v[i] <= k) {
				if(j == n - 1) {
					temp = j - i + 1;
					result = max(temp, result);
				}
				else {
					continue;	
				}
			}
			else {
				temp = j - i;
				result = max(temp, result);
				break;
			}
		}
	}
	
	cout << result << endl;
}

• 문제 출처 : https://www.acmicpc.net/problem/12005
• 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.