Gridland Metro

https://www.hackerrank.com/challenges/gridland-metro/problem
분류 : Search

문제 설명

n x m 으로 나타낼 수 있는 Gridland 에는 수평 방향의 철길들이 있다.
즉 각각의 철길은 (r, c1, c2) 로 나타낼 수 있다. r 은 row , c1 은 start 지점, c2 는 end 지점을 나타낸다.
철길이 있는 곳을 제외하고 lampost 들을 설치하려고 하는데, 설치할 수 있는 lampost 의 개수는 ?

Input 예시

첫 줄에는 n, m, k 가 주어진다. k 는 철길의 개수다.
다음에는 k 개의 철길 정보가 주어진다. 철길 정보는 r , c1, c2 순으로 입력된다.

1 <= n, m <= 10 ^9 임을 유의하자.

같은 행에 여러개의 철길이 있을 수 있고, 겹쳐 있을 수도 있다..
입력의 자세한 예시와 결과는 위에 링크를 참고하도록 하자. 예시가 잘 나와 있다.

풀이

n x m 의 범위가 int 를 넘기 때문에 정답도 당연히 int 의 범위를 넘을 수 있다.
이것때문에 계속 틀렸다.ㅠㅠ
정답을 저장하는 변수를 long long 으로 선언해줘야 한다. (long long 은 64bit -> 10^18 까지 커버 가능)

 

풀이 과정은 대략 다음과 같다.

n x m 한 값을 먼저 ans 변수에 담고, 기차가 차지하는 면적을 빼주는 식으로 구현했다.

 

1. 먼저 입력을 row 순으로 오름 차순 정렬한다.
2. 같은 row 인 기차 정보들끼리 있을 수 있도록 vector 에 담는다.

ex) (1,1,3) (2,1,2) , (1,2,4) 이렇게 input 이 들어오면 vector[0] = [(1,3),(2,4) ], vector[1] = [(1,2)] 이런 식으로

여기선 trains 라는 vector 자료형에 담았다. trains 는 pair 로 이루어진 vector 를 담는다.

using train = vector<pair<int,int>>;
vector<train> trains; //store train's start, end point in row
for(vector<int>& info : track) {
        if(info[0] != cur_row) {
            trains.emplace_back();
            cur_row = info[0];
        }
        (*(trains.end()-1)).emplace_back(info[1], info[2]);
    }

 

3. 각 row 정보를 돌면서 기차가 차지하고 있는 칸의 개수를 센다. 겹쳐있는 기차는 합친다고 생각하면 된다.

 

3의 과정이 이 문제의 핵심 알고리즘이다.
기차가 겹쳐있을 수 있기 때문에, 이를 고려해야 한다. 나는 discussion 을 참고해 stack 을 사용했다.

 

1. stack 에 row 의 제일 첫번째 기찻길 정보를 넣는다.
2. row 에 있는 기찻길을 순회하면서 다음의 과정을 반복한다.
   2-1. 현재 기찻길의 시작점이 stack top 에있는 기찻길의 시작점과 끝점 사이에 있는 점이라면
   2-2. 해당 점의 끝점이 stack top 에 있는 끝점보다 크다면 끝점을 갱신해준다.
   2-3. 2-1 에 해당하지 않는다면, 해당 정보를 stack 에 넣는다.
3. stack 에 있는 기찻길 정보를 돌면서 ans 를 갱신한다.

전체 코드

#include<iostream>
#include <vector>
#include <algorithm> //sort
#include <stack>
using namespace std;

using train = vector<pair<int,int>>;

// Complete the gridlandMetro function below.
long long gridlandMetro(int n, int m, int k, vector<vector<int>> &track) { // row c1 c2
    long long ans = ((long long)n)*((long long)m); //10^18

    auto comp = [](vector<int> &a,vector<int> &b){
        if(a[0] == b[0]){
            if(a[1] == b[1])
                return a[2] < b[2];
            else 
                return a[1] < b[1];
        } else {
            return a[0] < b[0];
        }
    };
    sort(track.begin(), track.end(),comp);
    vector<train> trains; //store train's start, end point in row
    int cur_row = 0;

    for(vector<int>& info : track) {
        if(info[0] != cur_row) {
            trains.emplace_back();
            cur_row = info[0];
        }
        (*(trains.end()-1)).emplace_back(info[1], info[2]);
    }

     for(train &t : trains) {
        stack<pair<int,int>> temp;
        temp.emplace(move(t[0]));
        int s  = t.size();
        for(int i=1; i<s; i++) { // (1,5) |  (1,2) (1,3) (2,3) (5,5)
            if( (t[i].first >= temp.top().first) && (t[i].first <= temp.top().second) ) {
                if(t[i].second > temp.top().second) {
                    temp.top().second = t[i].second;
                }
            } else {
                temp.emplace(move(t[i])); //해당안 되면 stack 에 push
            }
        }
        while(!temp.empty()) {
                ans-= (temp.top().second - temp.top().first + 1);
                temp.pop();
            }
    }

    return ans;
}


int main() {
    int n,m,k;
    cin >> n >> m >> k;
    vector<vector<int>> input(k);
    for(int i=0; i<k; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        input[i] = {a,b,c};
    }

    cout << gridlandMetro(n,m,k,input) << "\n";

}