[Coding Test] Algorithm(3)

1. 스위핑 (Sweeping)

스위핑은 "쓸다"를 의미한다. 스위핑 알고리즘이란 말 그대로 한 쪽 방향부터 시작해서 다른 방향으로 스캔해가면서 쓸어가는 것이다.

이 알고리즘은 특정한 자료구조나 구체적인 코드가 있는 것은 아니다. 단지, 한쪽 방향에서 시작해서 다른 방향으로 차근차근 해결해 나가는 기법이다.

이러한 특성 때문에, 보통 좌표와 관련있는 문제가 많이 보인다.

시간 복잡도는 nlogn이다.

2. 실전문제

선 긋기 (백준 2170)

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class P2170_선긋기 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            arr[i][0] = x;
            arr[i][1] = y;
        }
        Arrays.sort(arr, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) return o1[1] - o2[1];
                else return o1[0] - o2[0];
            }
        });
        int min = arr[0][0];
        int max = arr[0][1];
        int len = max - min;
        for (int i = 0; i < N; i++) {
            if (min <= arr[i][0] && max >= arr[i][1]) continue;
            else if (arr[i][0] < max && arr[i][1] > max) {
                len += arr[i][1] - max;
            } else if (arr[i][0] >= max) {
                len += arr[i][1] - arr[i][0];
            }
            max = arr[i][1];
            min = arr[i][0];
        }
        bw.write(len + "");
        bw.flush();
        bw.close();
        br.close();
    }
}