[백준][C++] 13334 철로

www.acmicpc.net/problem/13334

13334번: 철로

 

 

 

알고리즘 종류

    - 우선순위 큐

    - 정렬

    - 자료구조

 

 

 

사고 과정

    1. 도착 위치를 기준으로 오름차순 정렬한다. (출발 위치를 기준으로 오름차순해서 풀어보면 알겠지만, 출발 위치 + d로 범위를 탐색하면 출발 위치가 작은 사용자를 고려할 수 없다. 그래서 도착 위치를 기준으로 오름차순 정렬한다.)

    2. 하나씩 가져온다.

        2-1. 도착 위치 - 출발 위치가 철도 선분보다 크면 우선순위 큐에 넣어줄 필요가 없다.

        2-2. 철도 선분보다 작다면, 우선순위 큐에 도착 위치를 넣는다.

    3. 우선순위 큐를 순회하면서 현재 들어갈 사용자의 도착 위치 - d의 값보다 작은 이전 사용자들의 시작 위치를 제거한다.

    4. 우선순위 큐의 크기로 최대 사용자 수를 갱신한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
 
using namespace std;
 
int n, d;
int answer = 0;
vector<pair<int, int> > v;
priority_queue<int> pq;
 
 
bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.second == b.second) 
        return a.first < b.first;
    else 
        return a.second < b.second;
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> n;
    int s, e;
    for(int i=0; i<n; i++){
        cin >> s >> e;
        if(s < e) v.push_back({s, e});
        else v.push_back({e, s});
    }
    cin >> d;
    
    // 도착 위치를 기준으로 오름차순 정렬 그리고 출발 위치를 기준으로 오름차순 정렬  
    sort(v.begin(), v.end(), cmp);
    
    // 도착 위치가 빠른 순서대로 하나씩 뽑는다. 
    for(int i=0; i<v.size(); i++){
        int start = v[i].first;
        int end = v[i].second;
        
        // 길이가 철도 선분 d보다 크다면 pq에 넣지 않는다.  
        if(end-start <= d) pq.push(-start);
        else continue;
        
        // pq에는 출발 위치가 저장되어 있다.
        // 다음으로 들어갈 사람의 도착 위치에서 -d한 위치과 저장된 출발 위치를 비교 
        while(!pq.empty()){
            if(-pq.top() < end-d) pq.pop();
            else{
                answer = max(answer, (int)pq.size());
                break;
            }
        }
        
    }
    
    cout << answer;
}

 

 

 

시행착오

    - 이전에 풀이한 '싸지방에 간 준하'에 이어서 풀어본 우선순위 큐 문제이다. 역시나 어려웠다. 솔직히 이런 문제를 어떤 유형으로 부르는지도 몰랐지만 검색을 통해서 알게 되었다. '라인 스위핑'이라고 알게 되었다. 이런 유형의 문제는 정렬과 우선순위 큐를 이용한고 한다. 

    - 지금까지 내가 정립해본 풀이 과정은 다음과 같다.

        1. 시작 또는 끝 기준으로 정렬한다.

        2. 정렬에 사용된 기준이 아닌 다른 기준을 우선순위 큐에 저장한다. 예를 들어, 정렬에서 끝을 사용했으면, 우선순위 큐에서는 시작을 넣는다.

        3. 우선순위 큐에서 꺼내서 문제에서 요구하는 값과 비교한다.

    - 이 문제를 우선순위 큐를 사용하지 않아도 답을 낼 수 있지만, 시간이 오래 걸린다. 왜냐하면, 시간 복잡도 n^2이 되기 때문이다. 그래서 시작 위치를 우선순위 큐에 저장하여 철도 선분의 길이와 비교하면 nlogn으로 해결할 수 있다.

   - 문제 이해와 풀이 이해에 도움을 주신 블로그를 남겨놓겠습니다. 감사합니다.