2170번: 선 긋기

문제

매우 큰 도화지에 자를 대고 선을 그으려고 합니다. 선을 그을 때에는 이미 선이 있는 위치에 겹쳐서 그릴 수도 있는데, 여러 번 그은 곳과 한 번 그은 곳의 차이를 구별할 수 없습니다. 이와 같이 선을 그었을 때, 그려진 선(들)의 총 길이를 구하는 프로그램을 작성하는 문제입니다.

• 입력: 첫째 줄에 선을 그은 횟수 N (1 ≤ N ≤ 1,000,000)이 주어집니다. 둘째 줄부터 N개의 줄에 선을 그을 때 선택한 두 점의 위치 x, y (-1,000,000,000 ≤ x < y ≤ 1,000,000,000)가 주어집니다.
• 출력: 첫째 줄에 그은 선의 총 길이를 출력합니다.

링크: https://www.acmicpc.net/problem/2170

풀이: 정렬 및 라인 스위핑 (Line Sweeping)

주어진 선분들을 정렬한 뒤, 시작점부터 끝점까지 한 번에 훑으면서(Sweeping) 겹치는 구간을 병합해 나가는 방식입니다.

• 정렬 기준: 먼저 주어진 선분들을 '시작점' 기준으로 오름차순 정렬합니다. 시작점이 같다면 '끝점' 기준으로 오름차순 정렬합니다.
• 구간 병합 (Sweeping):
  1. 첫 번째 선분의 시작점을 s, 끝점을 e로 설정합니다.
  2. 다음 선분부터 순회하며, 현재 탐색 중인 선분의 시작점(a[i][0])이 현재까지 병합된 구간의 끝점(e)보다 작거나 같다면 겹치는 구간입니다. 이 경우 e를 Math.max(e, a[i][1])로 갱신하여 구간을 연장합니다.
  3. 만약 현재 탐색 중인 선분의 시작점이 e보다 크다면, 겹치지 않는 새로운 선분이 시작되는 것입니다. 지금까지 병합된 구간의 길이(e - s)를 정답(ans)에 누적하고, s와 e를 새로운 선분의 정보로 갱신합니다.
• 마지막 처리: 반복문이 종료된 후, 마지막으로 저장되어 있던 구간의 길이를 정답에 더해줍니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       int[][] a = new int[n][2];
       for (int i = 0; i < n; i++) {
          StringTokenizer st = new StringTokenizer(br.readLine());
          a[i][0] = Integer.parseInt(st.nextToken());
          a[i][1] = Integer.parseInt(st.nextToken());
       }

       // 시작점을 기준으로 오름차순 정렬, 시작점이 같으면 끝점을 기준으로 오름차순 정렬
       Arrays.sort(a, (o1, o2) -> {
          if (o1[0] == o2[0]) {
             return o1[1] - o2[1];
          }
          return o1[0] - o2[0];
       });

       int ans = 0;
       int s = a[0][0], e = a[0][1];
       for (int i = 1; i < n; i++) {
          if (a[i][0] > e) {
             ans += e - s;
             s = a[i][0];
             e = a[i][1];
          } else {
             e = Math.max(e, a[i][1]);
          }
       }

       ans += e - s;
       bw.write(ans + "\n");

       bw.flush();
    }
}

알고리즘 분류

정렬 (Sorting), 스위핑 (Sweeping)