[백준] 선 긋기 2170번 (C++) 라인스와핑

출처 :https://www.acmicpc.net/problem/2170

풀이 방법

라인스와핑 문제로 경우를 나누면 탐색 한 번으로 풀이할 수 있다.

먼저 선을 시작 좌표, 마지막 좌표 기준으로 정렬한다.

그 후 줄이 끊기는 경우와 연장되는 경우를 나누어 풀이하면 된다.

줄이 연장이 되려면 현재 줄의 end보다 다음 줄의 시작 부분의 좌표가 작아야 한다. 

그리고 현재 줄의 마지막과 다음 줄의 마지막 중 좌표가 큰 것을 end 좌표로 설정한다.

 

끊기는 경우는 다음 시작 좌표가 현재 end좌표보가 큰 경우로 이때 끊긴 줄의 길이를 더해주고 start, end값을 초기화해준다.

 

루프를 다 돈 후 마지막 줄에 대해 더해주는 과정이 필요하다.

 

입력이 많은 문제이므로 아래 코드를 추가하지 않으면 시간초과가 발생한다.

 

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

전체 코드

 

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

using namespace std;

int N ,ans = 0;
vector<pair<int, int> > lines;


bool cmp(pair<int, int> a, pair<int, int> b) {

    if (a.first < b.first) {
        return true;
    }
    else if (a.first == b.first) {
        if (a.second < b.second) return true;
        else return false;
    }
    else return false;
}
void sol() {
    sort(lines.begin(), lines.end(), cmp);
    int start = lines[0].first, end = lines[0].second;
    for (int i = 1;i < N;i++) {
        if (lines[i].first <= end) { // 줄이 연장되는 경우
            end = max(lines[i].second, end);
        }
        else { // 줄이 끊기는 경우
            ans += end - start;
            start = lines[i].first;
            end = lines[i].second;
        }
    }
    ans += end - start;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0;i < N;i++) {
        int a, b;
        cin >> a >> b;
        lines.push_back(make_pair(a, b));
    }

    sol();
    cout << ans << endl;
    return 0;
}