BOJ 2568 - 전깃줄 - 2 링크
(2023.05.03 기준 P5)

문제

두 전봇대 A와 B 사이에 전깃줄이 N개가 있다. 그리고 전봇대에 연결되는 한 위치에 두 개 이상의 전깃줄이 연결되지 않는다. 이 때, 전깃줄이 교차하지 않도록 제거해야 하는 최소 개수의 전깃줄 출력

알고리즘

O(n log n) LIS

풀이

큰 틀은 BOJ 2565 - 전깃줄 풀이와 같다.
저 문제와 다른 점은 큰 범위. 그리고 실제로 제거해야 하는 전깃줄의 위치를 출력해야 한다.

A 전봇대에 연결되는 위치의 번호를 기준으로 오름차순으로 정렬하여 B 전봇대에 연결되는 위치의 번호가 오름차순이 되는 전깃줄들의 가장 큰 집합을 구해야 한다. 이는 즉, B 전봇대에 연결되는 위치의 번호로 하여금 가장 긴 증가하는 부분 수열(LIS)을 구해야 하는 것이다.

하지만 N은 최대 100,000이다. 그러므로 O(N log N) LIS 알고리즘으로 구해야 한다.
여러 방법이 있다고 알려져 있지만, 가장 유명하고 쉬운 방법은 이분 탐색을 이용한 방법이다.

수열의 앞에서부터 원소가 들어갈 수 있는 가장 작은 인덱스를 이분 탐색으로 찾아 길이를 늘려가는 것이다. 이는 길이만 구할 수 있는데 여기서 각 수열의 원소마다 찾았던 인덱스를 저장해놓고 역추적을 하면 실제 LIS를 구할 수 있게 된다. 이는 코드를 보고 참고.

이 문제는 LIS를 제외한 나머지 전깃줄을 구해야 한다. 그러므로 LIS에 들어가는 원소를 제외한 나머지를 출력하면 된다.

코드

• C++

#include <bits/stdc++.h>
#define f first
#define s 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, A, B; i < N; i++) cin >> A >> B, pos.push_back({A, B});
    sort(pos.begin(), pos.end()); // A의 위치를 기준으로 정렬

    // LIS (O(N log N))
    vector<int> L; L.push_back(pos[0].s);
    int I[N], idx = 1; fill(I, I + N, 0);
    for (int i = 1; i < N; i++){
        // 지금까지 저장된 수열의 최댓값보다 더 크면 수열의 길이가 늘어난다.
        if (L.back() < pos[i].s){
            I[i] = idx++;
            L.push_back(pos[i].s);
        }
        // 수열에 들어갈 수 있는 인덱스를 찾아 들어간다.
        else{
            I[i] = lower_bound(L.begin(), L.end(), pos[i].s) - L.begin();
            L[I[i]] = pos[i].s;
        }
    }

    // 역추적
    vector<int> answer;
    for (int i = N - 1; i >= 0; i--){
        if (I[i] + 1 == idx) idx--; // LIS를 구성하는 원소면 패스
        else answer.push_back(pos[i].f); // 아니면 제거해야 하는 전깃줄이다.
    }

    int sz = answer.size();
    cout << sz << '\n';
    for (int i = sz - 1; i >= 0; i--) cout << answer[i] << '\n';
}

• Python

import sys; input = sys.stdin.readline
from bisect import bisect_left

N = int(input())
pos = sorted(tuple(map(int, input().split())) for _ in range(N)) # A의 위치를 기준으로 정렬

# LIS (O(N log N))
L = [pos[0][1]]
I = [0] * N; idx = 1
for i in range(1, N):
    # 지금까지 저장된 수열의 최댓값보다 더 크면 수열의 길이가 늘어난다.
    if L[-1] < pos[i][1]:
        I[i] = idx
        idx += 1
        L.append(pos[i][1])
    # 수열에 들어갈 수 있는 인덱스를 찾아 들어간다.
    else:
        I[i] = bisect_left(L, pos[i][1])
        L[I[i]] = pos[i][1]

# 역추적
answer = []
for i in range(N - 1, -1, -1):
    if I[i] + 1 == idx: # LIS를 구성하는 원소면 패스
        idx -= 1
    else: # 아니면 제거해야 하는 전깃줄이다.
        answer.append(pos[i][0])

print(len(answer))
print(*answer[::-1], sep = '\n')