[맞음?] [알고리즘] 백준 2170 선긋기 // 라인스위핑은 정렬

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

 

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,s,e,l,r,ret;
pair<int,int> p[1000000+4];

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

   cin>>n;

   for(int i=0;i<n;++i) {
      cin>>s>>e;
      p[i]={s,e};
   }

   sort(p,p+n);
   l=p[0].first; r=p[0].second;
   for(int i=1;i<n;++i) {
      if(r>=p[i].first && r<=p[i].second) { // 합칠수있으면 합치기
         r=p[i].second;
      }else if(r<p[i].first) { //못합치는경우 기존길이 더하기
         ret+=(r-l);
         l=p[i].first;
         r=p[i].second;
      }
   }

   ret+=(r-l);
   //마지막 남은길이 더하기
   cout<<ret;
   
   return 0;
}

 

* 25.2.20. 2회독

• 크게 3경우로 나눔
• 포함하는경우,
• 우측이 더 긴경우
• 하나도 안겹치고 새롭게 시작 하는경우

#include<bits/stdc++.h>
using namespace std; 

int n,ret;
vector<pair<int,int>> v;

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;
      v.push_back({a,b});
   }
   sort(v.begin(),v.end());
   int s = v[0].first;
   int e = v[0].second;
   ret+=(e-s);

   for(int i=1;i<v.size();++i) {
      // cout<<s<<" "<<e<<" "<<v[i].first<<" "<<v[i].second<<" " <<ret<<"\n";
      if(e>=v[i].second) {
         // cout<<"pass\n";
         continue;
      }
      if(v[i].first<=e && e<v[i].second) {
         ret+=(v[i].second-e);
         e=v[i].second;
         // cout<<"aaa\n";
         continue;
      }
      if(e<v[i].first) {
         ret+=(v[i].second-v[i].first);
         s=v[i].first;
         e=v[i].second;
         // cout<<"bb\n";
      }
   }
   
   cout<<ret;
}

 

* 큰돌풀이

• l과 r을 두고
• 새로운경우 -> 정답갱신, l,r 갱신
• r 만 바꾸면 되는경우 -> 정답갱신안함, r 만 갱신
• r과 l 에 집중
• 끝나고 남은 길이 더하기 필요

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <unordered_map>
using namespace std; 
typedef pair<int, int> P;
P L[1000004];
int n, from, to, l, r, ret; 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    cin >> n; 
    for(int i = 0; i < n; i++){ 
        cin >> from >> to;
        L[i] = P(from, to);
    }
    sort(L, L + n); 
    l = L[0].first; r = L[0].second; 
    for(int i = 1; i < n; i++){ 
        if(r < L[i].first){ 
            ret += (r - l); 
            l = L[i].first;
            r = L[i].second;
        }else if(L[i].first <= r && L[i].second >= r){ 
            r = L[i].second;
        }
    }
    ret += r - l;
    cout << ret << '\n';
}
/*
3
1 5
2 4
3 4 
*/