[SW Expert Academy] 9088. 다이아몬드 D4

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

 

 

문제 설명:

• Input
  • N: 다이아몬드의 개수
  • K: 크기 차

주어진 다이아몬드 중,  크기 차가 K 이하인 것들의 집합의 크기를 구하는 문제이다.

여기서 크기 차는, 해당 집합에서 최댓값과 최솟값의 차를 말한다.

즉, 집합 중, 최대값과 최솟값의 차가 k 이하인 집합 중 가장 크기가 큰 것의 크기를 출력하는 문제!

 

 

풀이:

투 포인터를 사용해서 빠르게 문제를 해결할 수 있다.

 

int l=0,r=0; 으로 두고, arr[r]-arr[l]의 값이 k 이상이면 l++하고, k 이하이면 결괏값을 업데이트해주고 r++을 해주면 된다.

 

현재 위치에서 최대 결과 값은 (r-l+1)이 된다.

 

 

<처음에 틀린 풀이>

처음에는 값을 정렬한 뒤,

int l=0, r=n-1; 으로 두고, 두 값의 차가 k가 넘으면, 둘 중 (중앙 쪽) 옆의 값과의 차가 큰 것을 이동시키는(버리는) 식으로 문제를 해결하려고 했었다. 

하지만, 이렇게 되면 다음과 같은 예외 케이스가 있을 수 있다.

 

n=6 k=4

1 5 10 11 19 20

 

 

 

소스 코드:

#include <iostream>
#include <cmath>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#define inf 987654321
using namespace std;


typedef pair<int, int> P;

int tc, n, k;
int arr[1002];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;

	for (int i = 1; i <= tc; i++) {
		cin >> n >> k;
		for (int j = 0; j < n; j++) {
			cin >> arr[j];
		}
		sort(arr, arr + n);
		int l = 0, r = 0;
		int res = 1;
		while (r<n) {
			if (arr[r] - arr[l] <= k) {
				res =max(res, r - l + 1);
				r++;
			}
			else l++;
		}
		cout << "#" << i << " " << res << '\n';
	}
	return 0;
}