라인스위핑, 투포인터

라인스위핑(line sweeping)

빗자루 쓸 듯 하나의 라인을 탐색하는 알고리즘입니다. 

보통 집합이나 교차점과 같은 기하 문제를 풀 때 사용되곤 하지만, 코딩테스트에서는 그 정도의 난이도로는 나오지 않습니다.

따라서 보통 최대 구간, 횟수 등을 찾는데 많이 쓰이는 알고리즘입니다.

 

예제 문제

철수는 도화지 위에 여러 번 선을 긋습니다.

• 한 선은 두 점 (a, b)로 표현됩니다.
• 여러 선이 겹쳐 그려지더라도, 겹친 구간은 한 번만 계산해야 합니다.

즉, 모든 선분을 합쳤을 때 총 길이를 구하는 문제입니다.

 

입력 조건

• 첫 줄: 선의 개수 N (1 ≤ N ≤ 1,000,000)
• 이후 N개의 줄: 두 정수 a, b (-1,000,000,000 ≤ a ≤ b ≤ 1,000,000,000)

출력 조건

• 겹치지 않게 계산한 선분의 총 길이

 

예제 입력

5
0 2
1 5
3 7
8 10
6 9

 

예제 출력

10

 

해당 문제를 단순하게 풀려면 선의 길이에 해당하는 포인트들을 마킹하는 방식이 있습니다.
예를 들어 1~3 의 선분이라면 mark[1] = mark[2] = mark[3] = 1; 과 같은 방식으로요.
하지만 해당 방식은 결국 20억가량의 모든 점을 체크해야하니 시간초과도 날 뿐더러 메모리 초과도 납니다.

따라서 이럴 땐 라인스위핑을 이용합니다. 입력을 받을 때마다 선분을 늘려두거나, 선분의 길이를 바로 ret에 계산해둡니다.
아래의 정답 코드로 바로 보시죠!

 

#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> P;
P L[1000004];
int n, from, to, l, r, ret;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> from >> to;
        L[i] = P(from, to);
    }

    sort(L, L + n); // 시작점 기준 정렬

    l = L[0].first, r = L[0].second;
    for (int i = 1; i < n; i++) {
        if (r < L[i].first) { // 안 겹침
            ret += (r - l);
            l = L[i].first;
            r = L[i].second;
        } else if (L[i].second > r) { // 겹침
            r = L[i].second;
        }
    }
    ret += (r - l);

    cout << ret << '\n';
}

 

---

투포인터(two pointer)

투포인터는 '정렬된 배열(선형 자료구조)'에서 2개의 포인터를 사용하여 특정 조건을 만족하는 부분 배열이나 값을 찾을 때 주로 사용되는 알고리즘입니다. 보통 정렬된 배열에서 두 수의 합 찾기, 연속된 부분배열의 합 찾기에 사용됩니다.

 

투포인터 알고리즘은 말 그대로 Left Pointer, Right Pointer 를 이용합니다. 

왼쪽 포인터(Left Pointer) : 배열의 시작 지점 -> 오른쪽으로 이동

오른쪽 포인터(Right Pointer) : 배열의 끝 지점 -> 왼쪽으로 이동

 

예제 문제

영희는 숫자를 좋아해서, 주어진 수열에서 두 수의 합이 X가 되는 쌍의 개수를 찾고자 합니다.

 

입력 조건

• 첫 줄: 수열의 크기 n
• 둘째 줄: 수열의 원소 (서로 다른 양의 정수, 1 ≤ a[i] ≤ 100,000)
• 셋째 줄: 정수 X (1 ≤ X ≤ 200,000)

출력 조건

• 합이 X가 되는 쌍의 개수

예제 입력

8
1 9 2 8 4 7 3 6
10

 

예제 출력

4

 

해당 문제도 nC2 를 하면 되므로 이중 반복문으로 풀어낼 수 있습니다. 하지만 n이 매우 클 경우 시간초과가 납니다.
시간 복잡도 자체가 O(n^2)이기 때문입니다.

따라서 이 문제를 해결하기 위해, 정렬 후 투포인터를 적용합니다.
정렬해둔뒤, 좌-우 포인터를 움직여가며 조건에 만족하는 값이 있는지를 판단합니다.

그럼 정렬하는데 걸리는 시간인 O(nlogn) + 탐색하는데 걸리는 시간인 O(n)이 걸리므로,
최종적으로 max(nlogn,n) ~= 보통 O(nlogn) 의 시간 복잡도를 갖게 됩니다.

정답 코드는 아래와 같습니다.

 

정답 코드

#include <bits/stdc++.h>
using namespace std;

int n, ret, x;

int main() {
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    cin >> x;

    sort(a.begin(), a.end());
    int l = 0, r = n - 1;

    while (l < r) {
        int sum = a[l] + a[r];
        if (sum == x) {
            ret++;
            r--; // 중복 방지 위해 r 이동
        } else if (sum > x) {
            r--;
        } else {
            l++;
        }
    }
    cout << ret << "\n";
}