[백준] 2170번 선 긋기

문제

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

 

풀이

 

시작하는 점을 1, 끝나는 점을 -1로 저장하고 스택을 이용해 겹치는 선분이 끝날 경우 길이를 구해줬습니다.

‎‎‎선분 A(1,3), 선분 B(4, 6) 을 예로 들면,

1. 정점 1 스택에 push

2. 정점 3 은 끝 점이므로 pop 하고 길이(3-1) 저장
3. 정점 4 은 시작점이므로 push

4. 정점 6 은 끝 점이므로 pop 하고 길이 (6,4) 저장

 

겹치는 경우도 손으로 해보면 올바르게 계산된다는 점을 알 수 있습니다.

 

소스코드

 

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

using namespace std;

int n;
vector<pair<int,int>> points;

int main(){

    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n;

    for(int i = 0; i < n; i++){

        int s, e;

        cin >> s >> e;

        points.push_back({s,1});
        points.push_back({e,-1});
    }

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

    stack<int> s;

    int ans = 0;
    int sNum = 0;
    for(int i = 0; i < points.size(); i++){
        if(!s.empty())
            sNum = s.top();

        if(points[i].second == 1){
            s.push(points[i].first);
        }else{
            s.pop();
        }

        if(s.empty()){
            ans += points[i].first - sNum;
        }
    }

    cout << ans;

    return 0;
}