BOJ 13334 - 철로 링크
(2023.08.08 기준 G2)

문제

n명의 사람들의 집, 사무실의 위치가 주어진다. 이 위치들은 수평선 상에 있는 서로 다른 점에 위치한다.
일직선 상의 어떤 두 점을 잇는 길이 d의 철로를 건설하려고 하는데, 이 때, 집과 사무실의 위치 모두 철로에 포함되는 최대 사람들의 수 출력

알고리즘

스위핑 및 우선순위 큐를 이용한 점 관리

풀이

위의 예시를 살펴보자.
길이 d의 선분을 주어진 위치들의 오름차순 순서대로 대보면, 2개 포함되는 색상의 수를 확인할 수 있다.

이를 그대로 코드로 구현하면 된다.

먼저, 위치들을 입력받아 인덱스와 함께 오름차순으로 정렬하자.
그리고 위치의 오름차순 순서대로 훑어보면서, d 이상 차이나는 왼쪽의 위치들은 제외한 다음에 2개 포함되는 인덱스의 수로 정답을 갱신하면 된다.
훑고 난 다음 왼쪽에 위치하는 위치들은 우선순위 큐로 관리하면 된다.

코드

• C++

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;

typedef pair<int, int> pii;

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

    int n; cin >> n;

    // 스위핑을 위해 모으고 정렬
    vector<pii> pos;
    for (int i = 0, h, o; i < n; i++){
        cin >> h >> o;
        pos.push_back({h, i});
        pos.push_back({o, i});
    }
    sort(pos.begin(), pos.end());

    int d, include[n], answer, result; cin >> d;
    fill(include, include + n, 0); // 집이나 사무실이 포함되는 횟수. 2가 되면 집과 사무실 전부 포함되는 것이다.
    answer = result = 0; // 집과 사무실 전부 포함되는 사람 수

    priority_queue<pii, vector<pii>, greater<pii>> leftmost;
    for (auto [p, i]: pos){

        // 현재 위치와 d보다 넘게 차이나는 위치들을 전부 제외
        while (!leftmost.empty() && p - leftmost.top().x > d){
            if (include[leftmost.top().y]-- == 2) // 제외함으로써 포함되는 횟수가 2 미만이 되는지 확인
                result--;
            leftmost.pop();
        }

        // 현재 위치를 넣음으로써 포함되는 횟수가 2가 되는지 확인
        leftmost.push({p, i});
        if (++include[i] == 2) result++;

        // 정답 갱신
        answer = max(answer, result);
    }

    cout << answer;
}

• Python

import sys; input = sys.stdin.readline
from heapq import heappop, heappush

n = int(input())

# 스위핑을 위해 모으고 정렬
pos = []
for i in range(n):
    h, o = map(int, input().split())
    pos.append((h, i))
    pos.append((o, i))
pos.sort()

d = int(input())
include = [0] * n # 집이나 사무실이 포함되는 횟수. 2가 되면 집과 사무실 전부 포함되는 것이다.
answer = result = 0 # 집과 사무실 전부 포함되는 사람 수

leftmost = []
for p, i in pos:

    # 현재 위치와 d보다 넘게 차이나는 위치들을 전부 제외
    while leftmost and p - leftmost[0][0] > d:
        if include[leftmost[0][1]] == 2: # 제외함으로써 포함되는 횟수가 2 미만이 되는지 확인
            result -= 1
        include[leftmost[0][1]] -= 1
        heappop(leftmost)

    # 현재 위치를 넣음으로써 포함되는 횟수가 2가 되는지 확인
    heappush(leftmost, (p, i))
    include[i] += 1
    if include[i] == 2:
        result += 1

    # 정답 갱신
    answer = max(answer, result)

print(answer)