[BOJ/C++] 2212 센서

시간 복잡도

• 정렬 2번, n번 탐색 2번 이므로 $O(nlogn + nlogn + n + n)$ 의 시간복잡도가 발생합니다.
• N이 최대 10,000 이기 때문에 시간은 충분합니다.

문제 접근법

• 만약 2개의 집중국이 있다면 센서들 중 가장 거리차가 큰 1개를 끊어준다면 거리가 최솟값이 됩니다.
• 즉 K개의 집중국이 있다면 K-1개의 가장 큰 거리차의 센서를 끊어주면 됩니다.

1. 센서들의 좌표를 오름차순으로 정렬하고 중복을 제거합니다.
2. 각 좌표의 거리차를 구한 후 오름차순으로 정렬합니다.
3. 뒤에서 K-1개를 제외한 거리차의 합을 구합니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<int> v(N);
    vector<int> diff;
    int answer = 0;

    for (int i = 0; i < N; i++)
        cin >> v[i];

    // 정렬 후 중복 제거
    sort(v.begin(), v.end());
    v.erase( unique(v.begin(), v.end()), v.end());


    for(int i=0; i<v.size()-1; i++)
        diff.push_back(v[i + 1] - v[i]);
    
    sort(diff.begin(), diff.end());


    for (int i = 0; i < static_cast<int>(diff.size()) - (K - 1); i++)
        answer += diff[i];

    cout << answer;

    return 0;
}