철로

백준 13334

GOLD II

1. 문제 내용
2. 해결 방안
3. 풀이 코드

---

문제 내용

문제 링크

해결 방안

n명의 사람들에 대한 각각 집과 사무소의 위치가 주어질 때, 임의의 길이의 선분에 대해 집과 사무소가 모두 포함되는 사람이 최대가 되는 경우를 찾는 문제이다. 집과 사무소는 일차원적인 직선 안에 위치해 있지만, 범위가 [−100,000,000, 100,000,000]의 정수이므로 브루트포스를 사용하는 것은 고민해볼 필요가 있다. 게다가 n의 볌위도 100,000이하의 자연수이기 때문에, 이 역시 일일이 범위 내에 있는 지 확인하는 것은 시간이 너무 많이 소요된다. 보다 최적화된 풀이를 위해 천천히 접근해보자.

우선, 철도에 가장 많은 사람을 포함하기 위한 접근 방식으로, 최소한 한 사람을 포함시키는 방법을 떠올릴 수 있다. 다르게 말하면, 주어진 집이나 사무소의 위치를 철도의 끝부분의 위치로 간주하는 것이다. 그리고, 해당 철도 안에 있는 사람들을 일일이 확인하는 방법 대신 정렬을 통해 전처리할 수 있다면 철도 안에 사람이 속해있는 지 보다 쉽게 확인할 수 있을 것이다. 마지막으로, 집과 사무소의 위치 중 방향을 통일하고, 반대 방향에 있는 집이나 사무소가 철도에 속해있는 지 확인하면 굳이 집과 사무소를 일일이 확인할 필요가 없어진다. 예로 들어, 왼쪽에 있는 집을 기준으로 철도를 오른쪽으로 설치하면, 오른쪽에 있는 사무소가 철도에 포함되면 왼쪽에 있는 집은 무조건 철도 선분에 포함될 것이기 때문이다.

이제 정리한 내용을 바탕으로 코드를 작성해보도록 한다. 집과 사무소의 위치를 입력받아, 집이나 사무소 중 왼쪽에 있는 것과 오른쪽에 있는 것을 각각 구분한다. 모든 위치를 입력받은 뒤에는, 오른쪽에 있는 것의 위치를 기준으로 오름차순으로 정렬한다. 그 다음, 우선순위 큐를 생성하여, 정렬된 위치들에 대해 순회하며 각각의 왼쪽에 있는 것의 위치를 저장한다. 각 위치에 대하여 오른쪽에 있는 것을 기준으로 왼쪽 방향으로 철도를 설정하고, 우선순위 큐의 맨 앞에 있는 가장 왼쪽에 있는 것이 철도를 벗어나면 해당 위치를 큐에서 꺼낸다. 철도 위치에 따라 큐 안의 원소들의 개수를 확인하고 최댓값을 갱신시켜주면, 모든 위치에 대해 확인했을 때의 최댓값이 문제에서 요구하는 답이 된다. 이러한 풀이와 관련된 다른 사람의 풀이로는 다음 블로그를 추천한다.

풀이 코드

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

using namespace std;
using pii = pair<int, int>;

// second에 대해 오름차순으로 정렬
// second 값이 같은 경우 first에 대해 오름차순
bool compare(pii a, pii b) {
    if(a.second == b.second)
        return a.first < b.first;
    return a.second < b.second;
}

int main() {
    // Fast IO
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(false);

    // 통근하는 사람의 수 n 입력
    int n;
    cin >> n;

    // 집과 사무실 위치 입력
    vector<pii> pos;
    int first, second;
    for(int i = 0; i < n; i++) {
        cin >> first >> second;
        // 더 왼쪽에 있는 것을 first에 저장
        if(first > second)
            pos.push_back({second, first});
        else
            pos.push_back({first, second});
    }
    
    // 철도 길이
    int d;
    cin >> d;

    // 집이나 사무소 중 오른쪽에 있는 것을 기준으로 오름차순 정렬
    // 오른쪽에 있는 것의 위치가 같으면, 그 외의 것이 더 왼쪽에 있는 사람을 앞으로 보냄
    sort(pos.begin(), pos.end(), compare);

    // 집이나 사무소 중 왼쪽에 있는 것들을 오름차순 정렬
    priority_queue<int, vector<int>, greater<int>> q;
    // 철도 안에 있는 것의 최댓값 저장
    int max_count = 0;
    for(int i = 0; i < n; i++) {
        // 철도의 범위 지정
        int end = pos[i].second;
        int start = end - d;

        // 현재 가장 왼쪽에 있는 사무실이나 집이 철도 범위를 벗어나면,
        // 해당 사람은 선분 내부에 없는 것으로 간주
        while(!q.empty() && q.top() < start)
            q.pop();

        // 만약 현재 왼쪽에 있는 것이 철도 범위 안에 있다면,
        if(pos[i].first >= start) {
            // 선분 안에 있는 것으로 간주
            q.push(pos[i].first);

            // 포함되는 사람의 최댓값 선택
            int count = q.size();
            max_count = max(count, max_count);
        }
    }

    // 최댓값 출력
    cout << max_count << endl;
    return 0;
}

---