[백준 13334] 철로

 

 자료 구조 문제다. 잊을만하면 접하게 되는 유형인데, 처음에 우선순위 큐가 아닌 일반 큐를 사용했다가 가차 없이 틀렸습니다를 받아서 좀 당황했다. 이후 우선순위 큐로 바꾸고 바로 통과할 수 있었다.

 

 입력받는 데이터의 양을 보면 알 수 있듯이, 모든 좌표를 시작점으로 해서 탐색해 보는 브루트 포스를 이용하면 시간 초과가 난다. 하지만 조금 생각해 보면 굳이 모든 지점을 확인할 필요는 없음을 알 수 있다. 정수 쌍이 많아봐야 100,000개고 그 정수 쌍에 나타나는 필요한 좌표들만 확인하면 되는 문제다.

 

 먼저 기준점 하나가 고정되면 철로의 길이를 이용해서 유효한 범위는 확정할 수 있으므로, 기준점을 정해 데이터셋을 정렬한 다음에 기준점이 변경될 때마다 그에 맞게 처리하면 되겠다고 생각할 수 있다.

 나는 기준점과 -d 해준 점의 범위를 유효한 범위로 두고 탐색하기 위해, 정수 쌍의 더 큰 점을 기준으로 오름차순 정렬했다. 이렇게 되면 좌표상에서 더 오른쪽에 있는 점을 기준으로 더 앞서 있는 정수 쌍이 배열의 앞쪽에 존재하게 된다.

 대략 위와 같은데, 위에 있을수록 배열의 앞에 놓이는 값이다. 나는 C++의 STL 내의 sort()와 Pair를 활용했기 때문에, 내 코드 내에서는 오른쪽 좌표가 같다면 왼쪽 좌표가 더 앞에 있는 정수 쌍이 배열의 앞에 놓여서 그림과는 좀 달라지긴 할 것이다.

 

 그래서 나는 이 배열의 처음부터 탐색하면서 오른쪽 점 좌표 값을 갱신해 가며, 유효한 범위에 있다면 왼쪽 점 좌표 값을 우선순위 큐에 넣어주었다.

 우선순위 큐에는 값이 작을수록 높은 우선순위를 가지게 해 뒀고, 따라서 현재 기준이 되는 오른쪽 점의 범위 내에 우선순위 큐에 들어있는 top 값이 존재하지 않는다면 우선순위 큐에서 pop 해줬다.

 추상화해서 나타내자면, 위처럼 d 값을 이용해서 매번 범위를 특정해서 우선순위 큐에 있는 값들을 하나씩 확인하며 제거해 버린다. pop 옆의 숫자는 pop 되는 순서인데, 여기서는 뚜렷하게 잘 나타나진 않지만 왼쪽 좌표 값이 앞에 있을수록 더 높은 우선순위를 가진다. 그렇게 해두면 우선순위 큐의 top이 범위 이내일 때는, 더 이상 pop 할 필요가 없어진다.

 

 이를 이용해 결과로 출력할 현재까지의 최대 크기를 매번 우선순위 큐의 size와 비교해 갱신해 주고, 모든 정수 쌍 순회 후에 출력해 주면 된다. 

 

 오랜만에 비교적 쉬운 문제를 풀어서 숨통이 트이는 느낌이었다. 그런데 입력 값으로 주어지는 데이터셋에 대해 h<=o이 보장되지 않는다는 건 좀 놓치기 쉬운 부분인 것 같다. 입력 예제 2를 통해서 바로 알 수 있어서 괜찮았지 만약 그런 예제가 없었다면 고생을 좀 했을 것 같다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

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

    int n, d;
    int h, o;
    cin >> n;
    vector<pair<int, int> > positions(n); //{o, h}

    for(int i=0; i<n; i++) {
        cin >> positions[i].first >> positions[i].second;
        if(positions[i].second>positions[i].first) {
            swap(positions[i].second, positions[i].first);
        }
    }
    cin >> d;

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

    priority_queue<int, vector<int>, greater<int> > pq;

    uint64_t maxNum = 0;
    int prev;
    for(int i=0; i<n; i++) {
        prev = positions[i].first-d;
        while(!pq.empty() && pq.top()<prev) {
            pq.pop();
        }
        if(positions[i].first-positions[i].second<=d) pq.push(positions[i].second);

        maxNum = max(maxNum, pq.size());
    }

    cout << max(maxNum, pq.size());

}