백준 12005 Diamond Collector [c++]

20 Jun 2022 in Develop / Solving

c++

문제 분석

• 베시가 다이아몬드를 진열할 건데, 다이아몬드가 균일해 보여야 한다.
• 그래서, 최대 크기의 다이아몬드와 최소 크기의 다이아몬드 크기 차이가 K 이하여야 한다.
• 최대로 전시할 수 있는 다이아몬드의 수를 구해라.

입력조건

다이아몬드의 수 N, 허용되는 크기 차이 K

풀이과정

• 입력받은 다이아몬드의 크기들을 오름차순으로 정렬한다.
• 투포인터로, 전시할 다이아몬드들의 맨 앞과 맨 뒤를 찍는다.

• 포인터 크기를 벌려가면서, 최대값을 찾는다.

• K가 0일 수 있다.

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, K;
    cin >> N >> K;

    vector<int> vec;
    for(int i = 0; i < N; i++) {
        int a;
        cin >> a;
        vec.push_back(a);
    }

    sort(vec.begin(), vec.end());

    int a = 0;
    int b = 0;
    int ans = 0;

    while(b < N) {
        if(vec[b] - vec[a] > K) a++;
        else {
            // cout << a << " " << b << endl;
            ans = max(ans, b++ - a + 1);
        }
    }
    cout << ans;
}