[백준] 6603 : 로또 - Java

• 백준 문제 URL

겹치는 선분들을 합쳐서 최소 총 길이를 구하는 문제
n개의 선분이 주어질 때, 겹치는 선분들을 병합하여 최종 선분들의 총 길이를 구함.

---

문제 접근

• 입력
  첫 줄에 선분 개수 $n$ (1 ≤ n ≤ 1,000,000)
  다음 $n$줄에 각 선분의 시작점 $x$와 끝점 $y$ (1 ≤ x < y ≤ 1,000,000)

  예를 들어,

  4
  1 3
  2 5
  3 5
  6 7

  입력 시, 겹치는 선분들을 병합하여 총 길이를 구해야 함.

• 출력
  병합된 모든 선분들의 길이 합을 출력함.

---

제출

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));
        
        int n = Integer.parseInt(br.readLine());
        
        List<Line> lineList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            lineList.add(new Line(x, y));
        }

        // x좌표 기준 오름차순, x가 같으면 y좌표 오름차순
        Collections.sort(lineList, new Comparator<Line>() {
            @Override
            public int compare(Line a, Line b) {
                if (a.x == b.x) {
                    return Integer.compare(a.y, b.y);
                }
                return Integer.compare(a.x, b.x);
            }
        });

        int total = 0;
        int currentStart = lineList.get(0).x;
        int currentEnd = lineList.get(0).y;

        // 첫 번째 선분은 current에 설정 후 i=1부터 시작
        for (int i = 1; i < n; i++) {
            Line line = lineList.get(i);

            if (line.x > currentEnd) {
                // 완전히 분리된 구간
                total += currentEnd - currentStart;
                currentStart = line.x;
                currentEnd = line.y;
            } else if (line.y > currentEnd) {
                // 겹치는 구간 → 끝점 확장
                currentEnd = line.y;
            }
            // line.y <= currentEnd → 완전 포함 → 무시
        }
        
        // 마지막 구간 길이 추가
        total += currentEnd - currentStart;
        
        System.out.println(total);
    }
}

class Line {
    int x, y;
    
    Line(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

---

핵심 개념

1. 구간 합치기(Interval Merging)
   겹치는 선분들을 하나로 병합하여 중복 길이를 제거함.
   [1,3], [2,5], [3,5] → [1,5]로 합침 (길이 4).

2. 정렬 기준

   • x좌표 오름차순으로 정렬하여 왼쪽부터 차례대로 처리함.
   • x가 같으면 y좌표 오름차순으로 정렬.

3. 현재 구간 추적 로직

   • currentStart, currentEnd: 현재까지 병합된 구간
   • 새 선분 처리:
     • line.x > currentEnd → 새 구간 시작
     • line.y > currentEnd → 구간 확장
     • 그 외 → 완전 포함 (무시)

4. 시간복잡도 최적화

   • 정렬: O(n log n)
   • 병합: O(n)
   • 총 O(n log n) — n=10^6에서도 충분히 통과함.

---

출력 예시

입력

4
1 3
2 5
3 5
6 7

출력

5

계산 과정:

[1,3] + [2,5] + [3,5] → [1,5] (길이 4)
[6,7] → 길이 1
총 길이: 4 + 1 = 5

---

정리

• 구간 합치기 패턴의 전형적인 문제임
• 정렬 → 현재 구간 추적 → 병합/확장/무시 3가지 케이스 처리