[BOJ] 23740 버스 노선 개편하기

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

23740번: 버스 노선 개편하기

---

문제

서강 나라에서는 일직선 도로를 따라 N개의 버스 노선을 운영 중이다. 필요할 때마다 노선을 새로 만든 탓에 겹치거나 중복되는 노선이 많다. 복잡한 버스 노선에 지친 시민들을 위해 버스 노선을 개편하기로 했다.

각 버스 노선은 세 정수 S, E, C로 나타낼 수 있으며, 구간 [S,E]를 요금 C로 운행한다는 뜻이다. 어떤 두 버스 노선의 구간이 한 점 이상에서 겹친다면, 두 구간을 합친 새 노선으로 대체한다. 이때 요금은 더 낮은 금액의 요금을 따르기로 했다. 버스 노선 개편은 구간이 겹치는 버스 노선이 없을 때까지 진행한다.

그림 D.1: 개편 전과 개편 후의 버스 노선도

버스 노선들의 정보가 주어지면, 개편이 끝난 후 버스 노선의 정보를 출력하는 프로그램을 작성하자.

---

입력

첫 번째 줄에 버스 노선의 수 N이 주어진다. (1≤N≤200000)

두 번째 줄부터 N개의 줄에 각 버스 노선을 나타내는 세 정수 S, E, C가 주어진다. (0≤S<E≤10^9, 1≤C≤10^9)

---

출력

첫 번째 줄에 개편이 끝난 후의 버스 노선의 수 K를 출력한다.

두 번째 줄부터 K개의 줄에 개편 후 각 버스 노선의 S, E, C를 S가 작은 순서대로 출력한다.

---

풀이

1. input을 S를 기준으로 오름차순 정렬한다.
2. 가장 앞에 있는 값의 S,E,C를 start,end,cost에 저장한다.
3. end보다 큰 S를 만날 때까지 다음 조건을 만족시키면서 반복문을 돈다.
    1. E가 end보다 클 경우 end를 E로 갱신한다.
    2. C가 cost보다 작을 경우 cost를 C로 갱신한다.
4. end 보다 큰 S를 만날 경우 start,end,cost를 ans벡터에 넣고 start,end,cost를 S, E, C로 갱신한다
5. 3,4과정을 반복하고 끝났을 경우 ans에 들어가지 않은 start,end,cost를 넣어준다.

 

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>
#include <set>

#define p(a, b) make_pair(a, b)
#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)
#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

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

bool cmp(pair<pair<int,int>,int > a, pair<pair<int,int>, int > b){
    return a.first.first<b.first.first;
}

void input() {
    cin>>N;
    int s,e,c;
    for(int i=0;i<N;i++){
        cin>>s>>e>>c;
        v.push_back(p(p(s,e),c));
    }
}

void init() {
}


void solution() {
    //S 기준으로 오름차순 정렬
    sort(v.begin(),v.end(),cmp);
    
    // 처음 S,E,C 값 start,end,cost에 저장
    int start=v[0].first.first,end=v[0].first.second,cost=v[0].second;
    
    for(int i=1;i<N;i++){
        int n_start=v[i].first.first,n_end=v[i].first.second,n_cost=v[i].second;
        if(n_start>end){ //S값이 end보다 클 경우
            ans.push_back(p(p(start,end),cost));
            start=n_start;
            end=n_end;
            cost=n_cost;
        }else{
            //E가 end보다 클 경우
            if(n_end>end) end=n_end;
            //C가 cost보다 작을 경우
            if(n_cost<cost) cost=n_cost;
        }
    }
    
    // ans에 들어가지 않은 start,end,cost를 넣어준다
    ans.push_back(p(p(start,end),cost));
    
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++) cout<<ans[i].first.first<<' '<<ans[i].first.second<<' '<<ans[i].second<<endl;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}