[C++] 백준 2170번: 선 긋기

문제

난이도 : 골드 5
백준 2170번 : 선 긋기

코드

#include <bits/stdc++.h>

using namespace std;

int N;
vector<pair<int, int>> v;

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

    cin >> N;

    for (int i = 0; i < N; i++)
    {
        int x, y;
        cin >> x >> y;
        v.push_back({ x, y });
    }

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

    int start = INT_MIN;
    int end = INT_MIN;
    int length = 0;

    for (int i = 0; i < N; i++)
    {
        if (end >= v[i].second) continue;

        start = max(v[i].first, end);
        end = max(v[i].second, end);

        length += (end - start);
    }

    cout << length;

    return 0;
}

풀이

라인 스위핑으로 푸는 문제
pair<int, int> 형으로 벡터에 선을 입력받는다. 입력받고 선의 시작 위치로 오름차순으로 정렬했다.
배열로 풀면 시간초과가 나는 문제므로 나는 그은 선의 시작 위치와 끝을 start와 end 변수로 나타냈다.
이때 선의 시작이 -10억 이하이므로 초기화를 INT_MIN 값으로 해주었다.
벡터의 0번째 인덱스부터 탐색을 시작하자.
만약 end가 현재 선의 끝보다 오른쪽에 있다면 넘긴다. 왜냐면 end 변수는 이때까지 내가 그은 선의 끝이기 때문에 현재 선의 끝이 end의 왼쪽에 있으면 이미 그린 선이다.
start는 현재 선의 시작 위치와 end의 최댓값을 대입. 이때 까지 그은 선의 끝이 현재 선의 왼쪽에 있다면 새로 그어야 되는 선임.(이때 end는 그 전 선까지의 끝점이다)
end에는 현재 선의 끝 위치와 end의 최댓값을 대입. 사실 위에 v[i].second와 end의 대소 비교를 이미 했기에 필요없는 코드인데 통일성을 위해,,
그리고 선의 길이에 end - start를 더해준다.

결과