[백준 1689] 겹치는 선분 - JAVA

문제 링크

문제 정의

1차원 좌표 평면 상에 $N$개의 선분이 주어질 때, 가장 여러 개의 선분이 겹치는 구간에서 겹치는 선분의 최대 개수를 구하는 문제입니다.

각 선분은 [시작점, 끝점]의 형태로 주어집니다.

선분의 끝점과 시작점이 닿는 경우(예: [1, 3]과 [3, 5])는 겹치는 것으로 취급하지 않습니다.

시간 복잡도

$N$의 최대 범위가 $1,000,000$이므로
모든 구간을 일일이 비교하는 $O(N^2)$ 완전 탐색 방식으로는 TLE가 발생합니다.
따라서 $O(N \log N)$ 이하의 시간 복잡도를 가지는 효율적인 알고리즘이 필요합니다.

---

접근 방법

이 문제는 시간의 흐름(좌표의 이동)에 따라 겹치는 선분의 개수를 세는
라인 스위핑(Line Sweeping) 개념에
투 포인터(Two Pointers) 기법을 접목하여
$O(N \log N)$의 시간 복잡도로 해결할 수 있습니다.

작성한 코드의 핵심 로직은 하나의 선분을 통째로 다루는 대신
선분의 '시작점'과 '끝점'을 분리하여 독립적인 이벤트로 취급하는 것입니다.

---

1. 시작점과 끝점 배열 분리 및 정렬

start[i] = Integer.parseInt(st.nextToken());
end[i] = Integer.parseInt(st.nextToken());

Arrays.sort(start);
Arrays.sort(end);

입력받은 선분들의 시작점은 start 배열에
끝점은 end 배열에 각각 저장한 뒤 오름차순으로 정렬합니다.

이렇게 하면 어떤 선분이 어디서 끝나는지와 무관하게,
단순히 "언제 새로운 선분이 겹치기 시작하는가"와
"언제 겹치던 선분이 빠져나가는가"를 순차적으로 확인할 수 있습니다.

---

2. 투 포인터를 활용한 스위핑 탐색

while (s < N) {
    if (start[s] < end[e]) {
        stack++;
        s++;
        max = Math.max(max, stack);
    }
    else {
        stack--;
        e++;
    }
}

s 포인터는 시작점 배열
e 포인터는 끝점 배열을 순회합니다.
현재 유지되고 있는 겹치는 선분의 개수는 stack 변수로 관리합니다.

start[s] < end[e] 인 경우

가장 빨리 끝날 예정인 선분(end[e])보다 새로운 선분(start[s])이 먼저 시작된 경우

• 선분이 하나 더 겹치게 된 것이므로 stack을 $1$ 증가
• 시작점 포인터 s를 다음으로 이동
• 최댓값 max을 갱신

start[s] >= end[e] 인 경우

새로운 선분이 시작되기 전에 기존에 있던 선분이 먼저 끝나버린 경우

• 겹치고 있던 선분이 하나 줄어든 것이므로 stack을 $1$ 감소
• 끝점 포인터 e를 다음으로 이동

모든 시작점을 순회할 때까지(s < N) 이 과정을 반복하면
단 한 번의 배열 순회만으로
선분이 가장 많이 겹쳤을 때의 개수를 깔끔하게 도출할 수 있습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	static StringTokenizer st;
	static int[] start;
	static int[] end;
	static int N;
	public static void main(String[] args) throws IOException {
		init();
		System.out.println(greedy());
	}

	static int greedy() {
		int s = 0;
		int e = 0;
		int stack = 0;
		int max = 0;;

		while (s < N) {
			if (start[s] < end[e]) {
				stack++;
				s++;
				max = Math.max(max, stack);
			}
			else {
				stack--;
				e++;
			}
		}

		return max;
	}

	static void init() throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		start = new int[N];
		end = new int[N];

		for (int i = 0; i < N; ++i) {
			st = new StringTokenizer(br.readLine());
			start[i] = Integer.parseInt(st.nextToken());
			end[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(start);
		Arrays.sort(end);
	}
}